답안 #3563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3563	2013-08-31T06:36:23 Z	mjy0503	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	176 ms	27212 KB

C

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
int n,top=-1,stack[100001];
using namespace std;
vector<int> list[100001],list2[100001];
map<pair<int,int>,bool> edge;
map<pair<int,int>,bool>::iterator it;
bool check[100001],flag,backedge;
void back(int k){
	int i;
	check[k]=1;
	for(i=0;i<list[k].size();i++){
		if(!check[list[k][i]]){
			list2[list[k][i]].push_back(k);
			edge.insert(make_pair(make_pair(list[k][i],k),false));
			back(list[k][i]);
		}
		else if(edge.find(make_pair(k,list[k][i]))==edge.end()){
			edge.insert(make_pair(make_pair(list[k][i],k),true));
			list2[list[k][i]].push_back(k);
		}
	}
	stack[++top]=k;
}
void flood(int k){
	int i;
	check[k]=1;
	for(i=0;i<list2[k].size();i++){
		if(!check[list2[k][i]]){
			it=edge.find(make_pair(k,list2[k][i]));
			if(it->second){
				if(backedge)
					flag=1;
				backedge=1;
			}
			flood(list2[k][i]);
		}
	}
	stack[++top]=k;
}
int main(){
	int m,i,a,b;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&a,&b);
		a--;b--;
		list[a].push_back(b);
		list[b].push_back(a);
	}
	for(i=0;i<n;i++){
		if(!check[i])
			back(i);
	}
	memset(check,0,sizeof(check));
	for(;top>=0;top--){
		backedge=0;
		if(!check[stack[top]])
			flood(stack[top]);
	}
	if(flag)
		printf("Not cactus\n");
	else
		printf("Cactus\n");
	return 0;
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6384 KB	Output is correct
2	Correct	0 ms	6384 KB	Output is correct
3	Correct	4 ms	7020 KB	Output is correct
4	Correct	4 ms	6900 KB	Output is correct
5	Correct	4 ms	6832 KB	Output is correct
6	Correct	4 ms	6912 KB	Output is correct
7	Correct	4 ms	7044 KB	Output is correct
8	Correct	4 ms	6912 KB	Output is correct
9	Correct	8 ms	6912 KB	Output is correct
10	Correct	120 ms	16812 KB	Output is correct
11	Correct	84 ms	15480 KB	Output is correct
12	Correct	132 ms	20252 KB	Output is correct
13	Correct	152 ms	19280 KB	Output is correct
14	Correct	152 ms	18712 KB	Output is correct
15	Correct	176 ms	23276 KB	Output is correct
16	Correct	128 ms	18340 KB	Output is correct
17	Correct	120 ms	20396 KB	Output is correct
18	Runtime error	176 ms	27212 KB	Program hung waiting for input
19	Halted	0 ms	0 KB	-