Submission #3847

#	Time	Username	Problem	Language	Result	Execution time	Memory
3847		imsifile	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	36 ms	6728 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 no, se[111111][2];

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;
	no=0;
	while(scn){
		s=stk[scn-1];
		if(ix[s]==-1){
			scn--;
			if(par[s]!=-1){
				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] || lv[e]>lv[s])continue;
		if(chk[e]){
			se[no][0]=s, se[no++][1]=e;
			if(lv[s]>lv[go[s]] || chk[s]==2 || chk[e]==2){
				printf("Not cactus");
				exit(0);
			}
			chk[s]=chk[e]=2;
			go[s]=e;
			continue;
		}
		lv[e]=lv[s]+1, go[e]=e, par[e]=s;
		stk[scn++]=e, chk[e]=1;
	}
	int i;
	for(i=0; i<no; i++){
		if(go[se[i][0]] != se[i][1]){
			printf("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);
	}
	printf("Cactus");
	return 0;
}

• Subtask 1: 0 / 1