답안 #3903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3903	2013-08-31T09:15:57 Z	wurikiji	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	4 ms	4460 KB

C

#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

vector<int> node[100001];
bool chk[100001];
int group[100001];
int cnt[100001];
stack<int> st;

int ret;
int grp;
void dfs(int x)
{
	st.push(x);
	chk[x] = true;
	for(int i = 0 ;i < node[x].size();i++)
	{
		if( !chk[node[x][i]] ) 
			dfs(node[x][i]);
	}
}
void dfs2(int x)
{
	chk[x] = true;
	group[x] = grp;
	for(int i = 0 ;i < node[x].size();i++)
	{

		if( !chk[node[x][i]] ) {
			cnt[node[x][i]]++;
			dfs2(node[x][i]);
		}
		else if( group[node[x][i]] == grp )
		{
			cnt[node[x][i]]++;
		}
	}
}
int main(void){
	int n, m;

	scanf("%d %d",&n, &m);

	for(int i = 0 ;i < m ;i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		node[a].push_back(b);
	}

	memset(chk,0,sizeof(chk));
	for(int i = 1; i <= n;i++)
	{
		if( !chk[i] ) 
			dfs(i);
	}

	memset(group, 0, sizeof(group));
	grp = 0;

	memset(chk,0,sizeof(chk));
	memset(cnt,0,sizeof(cnt));
	while(!st.empty()){
		int next = st.top();
		st.pop();
		if(!chk[next])
		{
			dfs2(next);
			grp++;
		}
	}
	for(int i = 1 ;i <=n;i++)
	{
		if( cnt[i] > 1 ) 
		{
			printf("Not cactus\n");
			return 0;
		}
	}
	printf("Cactus\n");
	return 0;
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4460 KB	Output is correct
2	Correct	0 ms	4460 KB	Output is correct
3	Incorrect	4 ms	4460 KB	Output isn't correct
4	Halted	0 ms	0 KB	-