답안 #3793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3793 2013-08-31T08:22:32 Z imsifile Cactus? Not cactus? (kriii1_C) C++
0 / 1
0 ms 6296 KB
#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]=1, go[k]=k;
	dd[0]=k, lst++;
	while(scn){
		s=stk[scn-1];
		if(ix[s]==-1){
			scn--;
			if(s!=k){
				if(lv[go[par[s]]]>lv[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]>lv[go[s]]){
				puts("Not cactus");
				exit(0);
			}
			go[s]=e;
			continue;
		}
		lv[e]=lv[s]+1, go[e]=e, par[e]=s;
		stk[scn++]=e, chk[e]=1, dd[lst++]=e;
	}
	int i;
	for(i=0; i<lst; i++){
		s=dd[i];
		if(lv[go[go[s]]] != lv[go[s]]){
			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 -