Submission #3793

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

C

#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;
}

• Subtask 1: 0 / 1