Submission #3662

#	Time	Username	Problem	Language	Result	Execution time	Memory
3662		pichulia	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	0 ms	8632 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 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++)
	{
		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 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[m[1]] = 1;
	stack[0][0] = m[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];
		if(r == vl[q])
			sp--;
		else
		{
			t = m[v[q][r]];
			if(t==s)
			{
				stack[sp-1][1]++;
			}
			else
			{
				if(mark[t] == 1)
				{
					break;
				}
				mark[t] = 1;
				stack[sp-1][1]++;
				stack[sp][0] = t;
				stack[sp][1] = 0;
				stack[sp][2] = q;
				sp++;
			}
		}
	}
	if(sp == 0)
		return 0;
	else
	{
		if(mode == 0)
		{
			for(i=0; i<sp; i++)
			{
				if(stack[i][0] == t)
					break;
			}
			for(;i<sp;i++)
			{
				m[stack[i][0]] = t;
			}
			remake_v();
		}
		return 1;
	}
}
void process()
{
	int i, j, k;
	k = find_cycle(0);
	
	if(k == 0)
		printf("Cactus");
	else
	{
		k = find_cycle(1);
		if(k == 0)
			printf("Cactus");
		else
			printf("Not cactus");
	}
}

void output()
{
}

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

• Subtask 1: 0 / 1