Submission #3714

#	Time	Username	Problem	Language	Result	Execution time	Memory
3714		arine	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	28 ms	1868 KiB

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 / 1