Submission #3856

#	Time	Username	Problem	Language	Result	Execution time	Memory
3856		The_KMJ_God	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	0 ms	4332 KiB

C

#include<stdio.h>
#include<vector>

using namespace std;

vector<int>g[100010];
int chk[100010],use[100010];
int n,m,cactus;
int f(int p,int pp)
{
	int count,i;
	count=0;
	chk[p]=1;
	use[p]=1;
	for(i=0;i<g[p].size();i++)
	{
		if(g[p][i]==pp)
			continue;
		if(chk[g[p][i]]==0)
		{
			if(use[g[p][i]]==0)
				count+=f(g[p][i],p);
		}
		else
			count++;
		if(count>1)
			break;
	}
	chk[p]=0;
	return count;
}
int main()
{
	int x,y,temp;
	int i;
	scanf("%d",&n);
	scanf("%d",&m);
	for ( i=0; i<m; i++ ) 
	{
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(i=1;i<=m;i++)
	{
		if(use[i]==0)
			temp=f(i,0);
		if(temp>1)
		{
			cactus=1;
			break;
		}
	}
	if(cactus==0)
		printf("Cactus");
	else
		printf("Not cactus");
}

• Subtask 1: 0 / 1