답안 #3763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3763	2013-08-31T08:12:52 Z	eldkqmfhf123	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	80 ms	11816 KB

C

#include<stdio.h>
#include<vector>
#include<deque>
#include<memory.h>
using namespace std;
int V,E;
vector<int> G[100001];
vector<int> rG[100001];
vector<int> vs;

bool used[100001];
int cmp[100001];

void add_edge(int from, int to)
{
	G[from].push_back(to);
	rG[to].push_back(from);

}
void dfs(int v)
{
used[v] = true;
for(int i=0;i<G[v].size();i++)
	if(!used[G[v][i]])
		dfs(G[v][i]);

vs.push_back(v);
}
void rdfs(int v,int k)
{
	used[v]=true;
	cmp[v] =k;
	for(int i=0;i<rG[v].size();i++)
		if(!used[rG[v][i]]) rdfs(rG[v][i],k);

}
int scc()
{
	memset(used,0,sizeof(used));
	vs.clear();
	for(int v=0;v<V;v++)
		if(!used[v])dfs(v);


	memset(used,0,sizeof(used));
	int k=0;

	for(int i=vs.size()-1;i>=0;i--)
		if(!used[vs[i]])rdfs(vs[i],k++);


	return k-1;

}

int main()
{
	scanf("%d %d",&V,&E);

	for(int i=0;i<E;i++)
	{	int tmp1,tmp2;
		scanf("%d %d",&tmp1,&tmp2);
		add_edge(tmp1,tmp2);
		add_edge(tmp1,tmp2);
	}
	if(scc()==1)
	printf("Not cactus\n");
	else
		printf("Cactus\n");
		
	return 0;

}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6380 KB	Output is correct
2	Correct	0 ms	6380 KB	Output is correct
3	Correct	0 ms	6656 KB	Output is correct
4	Correct	4 ms	6512 KB	Output is correct
5	Correct	4 ms	6512 KB	Output is correct
6	Correct	0 ms	6648 KB	Output is correct
7	Correct	0 ms	6648 KB	Output is correct
8	Correct	0 ms	6660 KB	Output is correct
9	Correct	0 ms	6648 KB	Output is correct
10	Correct	44 ms	10592 KB	Output is correct
11	Correct	32 ms	10592 KB	Output is correct
12	Correct	36 ms	9672 KB	Output is correct
13	Correct	56 ms	10624 KB	Output is correct
14	Correct	52 ms	10100 KB	Output is correct
15	Correct	60 ms	10796 KB	Output is correct
16	Correct	48 ms	9720 KB	Output is correct
17	Correct	40 ms	9492 KB	Output is correct
18	Correct	64 ms	11452 KB	Output is correct
19	Correct	80 ms	11816 KB	Output is correct
20	Correct	40 ms	9692 KB	Output is correct
21	Correct	52 ms	11456 KB	Output is correct
22	Correct	60 ms	10952 KB	Output is correct
23	Incorrect	0 ms	6380 KB	Output isn't correct
24	Halted	0 ms	0 KB	-