#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace::std;
int n;
vector<int> v[100005], w[100005];
int vl[100005],wl[100005];
int m[100005];
int get_mother(int i)
{
while(i != m[i])
i = m[i];
return i;
}
void input()
{
int i, j, k, l;
scanf("%d %d",&n, &k);
for(i=0; i<k; i++)
{
scanf("%d %d",&j,&l);
v[j].push_back(l);
v[l].push_back(j);
vl[j]++;
vl[l]++;
}
for(i=0; i<=n; i++)
m[i] = i;
}
void remake_v()
{
int i, j;
for(i=1; i<=n; i++)
{
for(j=0; j<vl[i]; j++)
{
w[m[i]].push_back(m[v[i][j]]);
wl[m[i]]++;
}
v[i].clear();
vl[i]=0;
}
for(i=1; i<=n; i++)
{
sort(w[i].begin(), w[i].end());
if(wl[i]>0)
{
if(w[i][0] != i)
{
v[i].push_back(w[i][0]);
vl[i]=1;
}
}
for(j=1; j<wl[i]; j++)
{
if(w[i][j] != w[i][j-1])
{
if(w[i][j] != i)
{
v[i].push_back(w[i][j]);
vl[i]++;
}
}
}
/*
printf("\n%d - %d : ",i,vl[i]);
for(j=0; j<vl[i]; j++)
printf("%d ",v[i][j]);
*/
}
}
int mark[100005];
int stack[100005][3];
int sp;
int find_cycle(int mode)
{
int q,r,s,t;
int i, j, k;
for(i=0; i<=n; i++)
mark[i] = 0;
sp=1;
mark[m[1]] = 1;
stack[0][0] = m[1];
stack[0][1] = 0;
stack[0][2] = -1;
while(sp>0)
{
q = stack[sp-1][0];
r = stack[sp-1][1];
s = stack[sp-1][2];
if(r == vl[q])
sp--;
else
{
t = m[v[q][r]];
if(t==s)
{
stack[sp-1][1]++;
}
else
{
if(mark[t] == 1)
{
break;
}
mark[t] = 1;
stack[sp-1][1]++;
stack[sp][0] = t;
stack[sp][1] = 0;
stack[sp][2] = q;
sp++;
}
}
}
if(sp == 0)
return 0;
else
{
if(mode == 0)
{
for(i=0; i<sp; i++)
{
if(stack[i][0] == t)
break;
}
for(;i<sp;i++)
{
m[stack[i][0]] = t;
}
remake_v();
}
return 1;
}
}
void process()
{
int i, j, k;
k = find_cycle(0);
if(k == 0)
printf("Cactus");
else
{
k = find_cycle(1);
if(k == 0)
printf("Cactus");
else
printf("Not cactus");
}
}
void output()
{
}
int main()
{
input();
process();
output();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
