답안 #3710

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3710 2013-08-31T07:47:53 Z pichulia Cactus? Not cactus? (kriii1_C) C++
0 / 1
400 ms 13244 KB
#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 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];
//		printf("%d   %d %d %d\n",sp,q,r,s);
		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
	{
		
		for(i=0; i<sp; i++)
		{
			if(stack[i][0] == t)
				break;
		}
		for(j=i; j<sp; j++)
		{
			if(c[m[stack[j][0]]] == 1)
				return 2;
		}
		for(;i<sp;i++)
		{
			m[stack[i][0]] = t;
		}
		c[t] = 1;
		remake_v();
	
		return 1;
	}
}
void process()
{
	int i, j, k;
	
	while(1)
	{
		k = find_cycle(0);
		/*
		for(i=1; i<=n; i++)
			printf("%d ",m[i]);
			*/
		if(k == 0)
		{
			printf("Cactus");
			break;
		}
		else if( k == 2)
		{
			printf("Not cactus");
			break;
		}
	}
}

void output()
{
}

int main()
{
	input();
	process();
	output();
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9024 KB Output is correct
2 Correct 0 ms 9024 KB Output is correct
3 Correct 8 ms 9288 KB Output is correct
4 Correct 0 ms 9300 KB Output is correct
5 Correct 8 ms 9156 KB Output is correct
6 Correct 4 ms 9156 KB Output is correct
7 Correct 300 ms 9420 KB Output is correct
8 Correct 212 ms 9288 KB Output is correct
9 Correct 132 ms 9288 KB Output is correct
10 Correct 44 ms 11928 KB Output is correct
11 Correct 28 ms 11776 KB Output is correct
12 Correct 44 ms 11964 KB Output is correct
13 Execution timed out 400 ms 13244 KB Program timed out
14 Halted 0 ms 0 KB -