#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");
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
