（并查集判环）NOJ-2297

时间限制(普通/Java) : 3000 MS/ 9000 MS 运行内存限制 : 65536 KByte
总提交 : 15 测试通过 : 1
比赛描述

oo喜欢和同学一起去宇宙中探索未知的事物。这天他发现宇宙中有双向虫洞和单向虫洞，可以传送到其他的星球上，但是因为虫洞十分不稳定，使用一次之后便会消失，现在他已经知道了所有虫洞所在的星球，他想知道他能不能选择一个星球，从这个星球出发并且最后回到这个星球。

输入

第一行一个整数T，表示case的个数(T<=15)。对于每个case，第一行三个整数，n,m1,m2(1<=n,m1,m2<=100000)，接下来m1行，每行两个整数u,v，表示一个双向虫洞连接u，v。接下来m2行，表示一个单向虫洞从u到v。

输出

对每个case，如果oo可以，则输出YES，如果不能，输出NO。

样例输入

1
2
5 2 1
1 2
1 2
4 5

样例输出

YES

这题判断两次环，一次是只能走一次的无向图，一次是有向图

/*
  ID: oodt
  PROG:
  LANG:C++
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<set>

using namespace std;

const int maxx=1000500;
int n,m,k;
int a[maxx];
int ans = 0,cnt = 0,pos = 0;
int l = 0,r = 0;
int m1,m2;

vector<int> G[maxx];
int par[maxx];
int in[maxx];
int ve[maxx];
priority_queue<int> q;

void init(){
    for(int i = 1; i <= n; i++) {
        G[i].clear();
        par[i] = i;
    }
    memset(in,0,sizeof(in));
    while(!q.empty()) q.pop();
//    ve.clear();
    memset(ve,0,sizeof(ve));
}
int find(int x){
    if(x == par[x]) return x;
    return par[x] = find(par[x]);
}

void tp(int n)
{
    for(int i = 1; i <= n; i++)
    {
        if(in[i] == 0) q.push(i);
    }
    k = 0;
    while(!q.empty()){
        int v = q.top();
        q.pop();
        //ve.push_back(v);
//        ve[v] = k--;
        k++;
        for(int i = 0; i < G[v].size(); i++)
        {
            int t = G[v][i];
            in[t]--;
            if(!in[t]) q.push(t);
        }
    }
}

int main()
{
#ifdef LOCAL
    freopen("/Users/ecooodt/Desktop/c++ and acm/_闆嗚2/talk_3/e/1.in","r",stdin);
    freopen("/Users/ecooodt/Desktop/c++ and acm/_闆嗚2/talk_3/e/1.out","w",stdout);
#endif
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m1,&m2);
        init();
        int fk = 0;
        for(int i = 0; i < m1; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            int fu = find(u);
            int fv = find(v);
            if(fu == fv){
                fk = 1;
                //  break;
            }
            else{
                par[fv] = fu;
            }
        }
        for(int i = 0; i < m2; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            int fu = find(u);
            int fv = find(v);
            if(fu == fv){
                fk = 1;
                //break;
            }
            else{
                G[fu].push_back(fv);
                in[fv]++;
            }
        }
        if(fk) {
            printf("YES\n");
            continue;
        }
        tp(n);
        if(k == n) {
            printf("NO\n");
        }
        else printf("YES\n");
    }
    return 0;
}