답안 #3848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3848 2013-08-31T08:48:31 Z wurikiji Cactus? Not cactus? (kriii1_C) C++
0 / 1
400 ms 5096 KB
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>

using namespace std;

vector<int> node[100001];
bool chk[100001];

int ret;
void dfs(int x, int src)
{
	chk[x] = true;
	for(int i = 0 ;i < node[x].size();i++)
	{
		if( node[x][i] == src )ret++;
		if( ret > 1 ) return;
		if( !chk[node[x][i]] ) 
			dfs(node[x][i], src);
		if( ret > 1 ) return;
	}
}
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);
	}

	for(int i = 1;i <= n ;i++)
	{
		ret = 0;
		memset(chk,0,sizeof(chk));
		dfs(i,i);
		if( ret > 1 )
		{
			printf("Not cactus\n");
			return 0;
		}
	}
	printf("Cactus\n");
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 3648 KB Output is correct
2 Correct 0 ms 3648 KB Output is correct
3 Correct 24 ms 3648 KB Output is correct
4 Correct 20 ms 3648 KB Output is correct
5 Correct 16 ms 3648 KB Output is correct
6 Correct 32 ms 3648 KB Output is correct
7 Correct 32 ms 3648 KB Output is correct
8 Correct 32 ms 3648 KB Output is correct
9 Correct 28 ms 3648 KB Output is correct
10 Execution timed out 400 ms 5096 KB Program timed out
11 Halted 0 ms 0 KB -