답안 #5121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5121	2014-02-10T04:10:55 Z	ainta	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	68 ms	9704 KB

C

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int par[100010], C;
bool chk[100010], ck;
vector<int>E[100010];
int n;
void DFS(int a, int p){
	par[a] = p;
	int i, x;
	for (i = 0; i < E[a].size(); i++){
		if (E[a][i] == p)continue;
		if (par[E[a][i]]){
			x = a;
			while (x != E[a][i]){
				if (chk[x])ck = true;
				chk[x] = true;
				x = par[x];
			}
			if (chk[x])ck = true;
			chk[x] = true;
			if (ck)return;
		}
	}
	for (i = 0; i < E[a].size(); i++){
		if (!par[E[a][i]]){
			DFS(E[a][i], a);
			if (ck)return;
		}
	}
}
int main(){
	int i, a, b, m;
	scanf("%d%d", &n, &m);
	while (m--){
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	DFS(1, 1);
	printf(ck ? "Not Cactus\n" : "Cactus\n");
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4040 KB	Output is correct
2	Correct	0 ms	4040 KB	Output is correct
3	Correct	0 ms	4172 KB	Output is correct
4	Correct	0 ms	4040 KB	Output is correct
5	Correct	0 ms	4040 KB	Output is correct
6	Correct	4 ms	4172 KB	Output is correct
7	Correct	4 ms	4172 KB	Output is correct
8	Correct	4 ms	4172 KB	Output is correct
9	Correct	4 ms	4172 KB	Output is correct
10	Correct	36 ms	6944 KB	Output is correct
11	Correct	28 ms	6792 KB	Output is correct
12	Correct	40 ms	7344 KB	Output is correct
13	Correct	40 ms	6976 KB	Output is correct
14	Correct	44 ms	6800 KB	Output is correct
15	Correct	44 ms	8136 KB	Output is correct
16	Correct	36 ms	6836 KB	Output is correct
17	Correct	32 ms	7348 KB	Output is correct
18	Correct	64 ms	9092 KB	Output is correct
19	Correct	68 ms	9704 KB	Output is correct
20	Correct	32 ms	7092 KB	Output is correct
21	Correct	56 ms	7180 KB	Output is correct
22	Correct	52 ms	8460 KB	Output is correct
23	Incorrect	0 ms	4040 KB	Output isn't correct
24	Halted	0 ms	0 KB	-