Submission #3714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3714	2013-08-31T07:49:11 Z	arine	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	28 ms	1868 KB

C

#include <cstdio>
#include <algorithm>
#define MAX_V 100005
using namespace std;

int V, E;
int parent[MAX_V];
int notMSTEdge[MAX_V];

int find(int target) {
	if(parent[target]==target) return target;
	return (parent[target]=find(parent[target]));
}
void unify(int a, int b) {
	int roota=find(a), rootb=find(b);
	parent[roota]=rootb;
}

int main() {

	scanf("%d %d", &V, &E);
	for(int i=0; i<V; ++i) parent[i]=i, notMSTEdge[i]=0;

	int a, b;
	for(int i=0; i<E; ++i) {

		scanf("%d %d", &a, &b);
		--a, --b;

		int roota=find(a), rootb=find(b);
		if(roota==rootb) {
			++notMSTEdge[a], ++notMSTEdge[b];
		} else {
			unify(a, b);
		}

	}

	for(int i=0; i<V; ++i)
		if(notMSTEdge[i]>=2) {
			printf("Not cactus");
			return 0;
		}
	
	printf("Cactus");

	return 0;

}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1868 KB	Output is correct
2	Correct	0 ms	1868 KB	Output is correct
3	Correct	0 ms	1868 KB	Output is correct
4	Correct	0 ms	1868 KB	Output is correct
5	Correct	0 ms	1868 KB	Output is correct
6	Correct	0 ms	1868 KB	Output is correct
7	Correct	0 ms	1868 KB	Output is correct
8	Correct	0 ms	1868 KB	Output is correct
9	Correct	0 ms	1868 KB	Output is correct
10	Correct	24 ms	1868 KB	Output is correct
11	Correct	20 ms	1868 KB	Output is correct
12	Correct	12 ms	1868 KB	Output is correct
13	Correct	24 ms	1868 KB	Output is correct
14	Correct	24 ms	1868 KB	Output is correct
15	Correct	20 ms	1868 KB	Output is correct
16	Correct	20 ms	1868 KB	Output is correct
17	Correct	16 ms	1868 KB	Output is correct
18	Correct	28 ms	1868 KB	Output is correct
19	Correct	24 ms	1868 KB	Output is correct
20	Correct	16 ms	1868 KB	Output is correct
21	Correct	28 ms	1868 KB	Output is correct
22	Correct	20 ms	1868 KB	Output is correct
23	Correct	0 ms	1868 KB	Output is correct
24	Incorrect	0 ms	1868 KB	Output isn't correct
25	Halted	0 ms	0 KB	-