Submission #3763

#	Time	Username	Problem	Language	Result	Execution time	Memory
3763		eldkqmfhf123	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	80 ms	11816 KiB

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 / 1