Submission #3741

#	Time	Username	Problem	Language	Result	Execution time	Memory
3741		pichulia	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	68 ms	12060 KiB

C

#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 c[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++)
	{
		w[i].clear();
		wl[i] = 0;
	}
	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 round(int st)
{
	int i, j, k;
	for(j=mark[st]-1; j<sp; j++)
	{
		if(c[stack[j][0]] == 1)
			return 1;
	}
	for(i=mark[st]-1;i<sp;i++)
	{
		m[stack[i][0]] = st;
		c[stack[i][0]]=1;
	}
//	remake_v();
	return 0;
}
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[1] = 1;
	stack[0][0] = 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];
	//	printf("%d   %d %d %d\n",sp,q,r,s);
		if(r == vl[q])
			sp--;
		else
		{
			t = v[q][r];
			if(t==s)
			{
				stack[sp-1][1]++;
			}
			else
			{
				if(mark[t] > 0)
				{
					k = round(t);
					if(k==1)
						return 1;
					stack[sp-1][1]++;
				}
				else
				{
					mark[t] = sp + 1;
					stack[sp-1][1]++;
					stack[sp][0] = t;
					stack[sp][1] = 0;
					stack[sp][2] = q;
					sp++;
				}
			}
		}
	}
	return 0;
}
void process()
{
	int i, j, k;
	
	k = find_cycle(0);
	if(k == 0)
	{
		printf("Cactus\n");
	}
	else
	{
		printf("Not cactus\n");
	}
	
}

void output()
{
}

int main()
{
	input();
	process();
	output();
	return 0;
}

• Subtask 1: 1 / 1