Submission #3878

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3878	2013-08-31T09:02:13 Z	Qwaz	Cactus? Not cactus? (kriii1_C)	C++	1 / 1	68 ms	11856 KB

C

#include <cstdio>
#include <vector>

struct edge {
	int to, num;
};

const int MAX=100020;

int n, m;
std::vector < edge > to[MAX];

void input(){
	scanf("%d%d", &n, &m);

	int i;
	for(i=0; i<m; i++){
		int f, s;

		scanf("%d%d", &f, &s);

		edge t;
		t.num = i;

		t.to = s;
		to[f].push_back(t);

		t.to = f;
		to[s].push_back(t);
	}
}

int parent[MAX], cycle[MAX], cFull=1, depth[MAX];
bool chk[MAX];

bool dfs(int now){
	int i;
	for(i=0; i<to[now].size(); i++){
		if(!chk[to[now][i].num]){
			chk[to[now][i].num] = 1;

			int next = to[now][i].to;
			if(parent[next] == 0){
				parent[next] = now;
				depth[next] = depth[now]+1;
				if(!dfs(next))
					return false;
			} else {
				int f = now, s = next;

				while(depth[f] > depth[s]){
					if(cycle[f] == 0)
						cycle[f] = cFull;
					else return false;
					f = parent[f];
				}
			
				while(depth[s] > depth[f]){
					if(cycle[s] == 0)
						cycle[s] = cFull;
					else return false;
					s = parent[s];
				}

				while(f != s){
					if(cycle[f] == 0)
						cycle[f] = cFull;
					else return false;

					if(cycle[s] == 0)
						cycle[s] = cFull;
					else return false;
				
					f = parent[f];
					s = parent[s];
				}

				if(cycle[f] == 0)
					cycle[f] = cFull;
				else return false;

				cFull++;
			}
		}
	}

	return true;
}

int main(){
	input();
	
	parent[1] = 1;
	puts(dfs(1)?"Cactus":"Not cactus");

	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4820 KB	Output is correct
2	Correct	0 ms	4820 KB	Output is correct
3	Correct	4 ms	4952 KB	Output is correct
4	Correct	0 ms	4820 KB	Output is correct
5	Correct	0 ms	4820 KB	Output is correct
6	Correct	0 ms	4952 KB	Output is correct
7	Correct	4 ms	4952 KB	Output is correct
8	Correct	4 ms	4952 KB	Output is correct
9	Correct	4 ms	4952 KB	Output is correct
10	Correct	40 ms	8120 KB	Output is correct
11	Correct	28 ms	8340 KB	Output is correct
12	Correct	28 ms	8916 KB	Output is correct
13	Correct	44 ms	8624 KB	Output is correct
14	Correct	52 ms	8688 KB	Output is correct
15	Correct	44 ms	9840 KB	Output is correct
16	Correct	40 ms	8156 KB	Output is correct
17	Correct	28 ms	8988 KB	Output is correct
18	Correct	56 ms	11072 KB	Output is correct
19	Correct	68 ms	11856 KB	Output is correct
20	Correct	40 ms	8620 KB	Output is correct
21	Correct	56 ms	8212 KB	Output is correct
22	Correct	48 ms	10252 KB	Output is correct
23	Correct	0 ms	4820 KB	Output is correct
24	Correct	0 ms	4820 KB	Output is correct
25	Correct	4 ms	5312 KB	Output is correct
26	Correct	40 ms	7592 KB	Output is correct
27	Correct	24 ms	6140 KB	Output is correct
28	Correct	36 ms	7196 KB	Output is correct
29	Correct	40 ms	7328 KB	Output is correct
30	Correct	48 ms	7724 KB	Output is correct
31	Correct	40 ms	7196 KB	Output is correct
32	Correct	52 ms	7592 KB	Output is correct
33	Correct	52 ms	7592 KB	Output is correct
34	Correct	56 ms	7592 KB	Output is correct