Exploration

2
5 2 1
1 2
1 2
4 5
4 2 2
1 2
2 3
4 3
4 1

YES
NO

Hint
If you need a larger stack size, 
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
 

/* ***********************************************
Author        :CKboss
Created Time  :2015年05月07日 星期四 22时48分45秒
File Name     :HDOJ5222.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

#pragma comment(linker, "/STACK:102400000,102400000") 

using namespace std;

const int maxn=1001000;

int fa[maxn];

int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

bool Union(int a,int b)
{
	a=find(a); b=find(b);
	if(a!=b) 
	{
		fa[a]=b; return true;
	}
	return false;
}

int n,m1,m2;

struct Edge
{
	int to,next;
}edge[2*maxn];

int Adj[maxn],Size;
int degree[maxn];
bool vis[maxn];

void init()
{
	for(int i=0;i<=n+10;i++) fa[i]=i;
	memset(Adj,-1,sizeof(Adj)); Size=0;
	memset(degree,0,sizeof(degree));
	memset(vis,false,sizeof(vis));
}

void Add_Edge(int u,int v)
{
	edge[Size].to=v;
	edge[Size].next=Adj[u];
	Adj[u]=Size++;
}


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    
	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d%d%d",&n,&m1,&m2);
		init();
		bool flag=false;
		for(int i=0;i<m1;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			if(Union(u,v)==false) flag=true;
		}
		
		for(int i=0;i<m2;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			if(flag) continue;
			u=find(u); v=find(v);
			if(u!=v) 
			{
				/// u--->v
				Add_Edge(v,u);
				degree[u]++;
			}
			else flag=true;
		}

		if(flag)
		{
			puts("YES"); continue;
		}

		queue<int> q;

		for(int i=1;i<=n;i++)
		{
			int u=find(i);
			if(vis[u]) continue;
			if(degree[u]==0)
			{
				q.push(u);
				vis[u]=true;
			}
		}

		while(!q.empty())
		{
			int u=q.front(); q.pop();
			u=find(u);
			for(int i=Adj[u];~i;i=edge[i].next)
			{
				int v=edge[i].to;
				v=find(v);
				degree[v]--;
				if(degree[v]==0) 
				{
					q.push(v);
					vis[v]=true;
				}
			}
		}

		bool ck=true;
		for(int i=1;i<=n&&ck;i++)
		{
			if(vis[find(i)]==false) ck=false;
		}

		if(ck) puts("NO");
		else puts("YES");
	}

    return 0;
}

HDOJ 5222 Exploration 并查集+拓扑排序 找环

原文：http://blog.csdn.net/ck_boss/article/details/45577963