답안 #3741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3741 2013-08-31T08:02:36 Z pichulia Cactus? Not cactus? (kriii1_C) C++
1 / 1
68 ms 12060 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 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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9024 KB Output is correct
2 Correct 0 ms 9024 KB Output is correct
3 Correct 0 ms 9156 KB Output is correct
4 Correct 4 ms 9024 KB Output is correct
5 Correct 4 ms 9024 KB Output is correct
6 Correct 4 ms 9156 KB Output is correct
7 Correct 4 ms 9156 KB Output is correct
8 Correct 0 ms 9156 KB Output is correct
9 Correct 4 ms 9156 KB Output is correct
10 Correct 32 ms 11928 KB Output is correct
11 Correct 32 ms 11776 KB Output is correct
12 Correct 40 ms 10872 KB Output is correct
13 Correct 40 ms 11136 KB Output is correct
14 Correct 52 ms 11004 KB Output is correct
15 Correct 52 ms 11400 KB Output is correct
16 Correct 44 ms 10872 KB Output is correct
17 Correct 40 ms 10740 KB Output is correct
18 Correct 60 ms 11796 KB Output is correct
19 Correct 68 ms 12060 KB Output is correct
20 Correct 32 ms 11008 KB Output is correct
21 Correct 60 ms 11796 KB Output is correct
22 Correct 44 ms 11532 KB Output is correct
23 Correct 0 ms 9024 KB Output is correct
24 Correct 0 ms 9024 KB Output is correct
25 Correct 0 ms 9288 KB Output is correct
26 Correct 48 ms 11796 KB Output is correct
27 Correct 24 ms 10080 KB Output is correct
28 Correct 40 ms 11400 KB Output is correct
29 Correct 52 ms 11400 KB Output is correct
30 Correct 48 ms 11532 KB Output is correct
31 Correct 32 ms 11400 KB Output is correct
32 Correct 52 ms 11796 KB Output is correct
33 Correct 56 ms 11796 KB Output is correct
34 Correct 56 ms 11796 KB Output is correct