Submission #4073

#	Time	Username	Problem	Language	Result	Execution time	Memory
4073		ainta	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	64 ms	10084 KiB

C

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[100001];
int n,m,p[100001],C[100001];
bool v[100001];
void DFS(int a){
	v[a]=true;
	int i,j;
	for(i=0;i<E[a].size();i++){
		if(v[E[a][i]] && E[a][i]!=p[a]){
			j=a;
			C[j]++;
			while(j!=E[a][i]){
				C[p[j]]++;
				j=p[j];
			}
		}
	}
	for(i=0;i<E[a].size();i++){
		if(!v[E[a][i]]){
			p[E[a][i]]=a;
			DFS(E[a][i]);
		}
	}
}
int main()
{
	int a,b,i;
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&a,&b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	DFS(1);
	for(i=1;i<=n;i++)if(C[i]>=2)break;
	if(i==n+1)printf("Cactus\n");
	else printf("Not cactus\n");
}

• Subtask 1: 1 / 1