#include<stdio.h>
#include<stdlib.h>
int n, m, par[111111], lv[111111], go[111111];
int ecn, enp[222222], prv[222222], top[111111];
int scn, ix[111111], stk[111111], chk[111111];
int lst, dd[111111];
void edg(int s, int e){
enp[ecn]=e, prv[ecn]=top[s], top[s]=ecn++;
}
void dfs(int k){
int s, e;
stk[scn++]=k, par[k]=-1, chk[k]=lv[k]=go[k]=1;
dd[0]=k, lst++;
while(scn){
s=stk[scn-1];
if(ix[s]==-1){
scn--;
if(s!=k){
if(go[par[s]]>go[s])go[par[s]]=go[s];
}
continue;
}
e=enp[ix[s]], ix[s]=prv[ix[s]];
if(e==par[s])continue;
if(chk[e]){
if(lv[s]>go[s]){
puts("Not cactus");
exit(0);
}
go[s]=lv[e];
}
lv[e]=go[e]=lv[s]+1, par[e]=s;
stk[scn++]=e, chk[e]=1, dd[lst++]=e;
}
int i;
for(i=0; i<lst; i++){
if(go[go[dd[i]]] != go[dd[i]]){
puts("Not cactus");
exit(0);
}
}
}
int main(){
int i, a, b;
scanf("%d%d", &n, &m);
for(i=0; i<n; i++)top[i]=-1;
for(i=0; i<m; i++){
scanf("%d%d", &a, &b), a--, b--;
edg(a,b), edg(b,a);
}
for(i=0; i<n; i++)ix[i]=top[i];
for(i=0; i<n; i++){
if(chk[i])continue;
dfs(i);
}
puts("Cactus");
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
6296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
