Submission #5121

#	Time	Username	Problem	Language	Result	Execution time	Memory
5121		ainta	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	68 ms	9704 KiB

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