답안 #5122

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

C

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int par[100010], C, chk[100010];
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]){
				chk[x]++;
				x = par[x];
			}
			chk[x]++;
		}
	}
	for (i = 0; i < E[a].size(); i++){
		if (!par[E[a][i]]){
			DFS(E[a][i], a);
		}
	}
}
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);
	for (i = 1; i <= n; i++)if (chk[i] >= 2)break;
	printf(i != n + 1 ? "Not Cactus\n" : "Cactus\n");
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4332 KB	Output is correct
2	Correct	0 ms	4332 KB	Output is correct
3	Correct	0 ms	4464 KB	Output is correct
4	Correct	0 ms	4332 KB	Output is correct
5	Correct	0 ms	4332 KB	Output is correct
6	Correct	0 ms	4464 KB	Output is correct
7	Correct	4 ms	4464 KB	Output is correct
8	Correct	4 ms	4464 KB	Output is correct
9	Correct	4 ms	4464 KB	Output is correct
10	Correct	40 ms	7236 KB	Output is correct
11	Correct	20 ms	7084 KB	Output is correct
12	Correct	40 ms	7636 KB	Output is correct
13	Correct	48 ms	7264 KB	Output is correct
14	Correct	48 ms	7084 KB	Output is correct
15	Correct	44 ms	8428 KB	Output is correct
16	Correct	40 ms	7128 KB	Output is correct
17	Correct	32 ms	7640 KB	Output is correct
18	Correct	56 ms	9384 KB	Output is correct
19	Correct	72 ms	9992 KB	Output is correct
20	Correct	40 ms	7388 KB	Output is correct
21	Correct	52 ms	7472 KB	Output is correct
22	Correct	56 ms	8748 KB	Output is correct
23	Incorrect	0 ms	4332 KB	Output isn't correct
24	Halted	0 ms	0 KB	-