HDU 5222 ——Exploration——————【并查集+拓扑排序判有向环】

Exploration

Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 194 Accepted Submission(s): 63

Problem Description

Miceren likes exploration and he found a huge labyrinth underground!

This labyrinth has

Input

The first line contains a single integer

Output

For each test queries, print the answer. If Miceren can do that, output "YES", otherwise "NO".

Sample Input

5 2 1

1 2

4 5

4 2 2

1 2

2 3

4 3

4 1

Sample Output

YES

Hint

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

题目大意：给你n个山洞，m1条无向隧道，m2条有向隧道，要你从一个山洞出发，经过除出发点外至少一个山洞回到出发点，一条隧道经过后会坍塌，问是否存在满足要求的路径。

解题思路：

首先对于所有的无向边，我们使用并查集将两边的点并起来。
若一条边未合并之前，两端的点已经处于同一个集合了，那么说明必定存在可行的环（因为这两个点处于同一个并查集集合中，那么它们之间至少存在一条路径）
如果上一步没有判断出环，那么仅靠无向边是找不到环的
考虑到，处于同一个并查集集合中的点之间必定存在一条路径互达，因此将一个集合的点合并之后（利用缩点），原问题等价于在新生成的有向图中是否有环
我们知道，有向无环图必定存在拓扑序，因此只需使用拓扑排序判定即可
时间复杂度

#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,m1,m2;
const int maxn=1e6+666;
int fa[maxn];       //并查集的father数组
bool flag[maxn];    //标记缩点、不重复加入队列
int indeg[maxn];    //记录入度
vector<int>Mp[maxn];//存有向边
int Find(int x){
    return fa[x]=fa[x]==x?x:Find(fa[x]);
}
bool Union(int x,int y){
    int fx,fy;
    fx=Find(x);
    fy=Find(y);
    if(fx<fy){
        fa[fy]=fx;
    }else if(fx>fy){
        fa[fx]=fy;
    }else{  //如果该无向边的两端同属一个集合，加入该边后，肯定形成环
        return true;
    }
    return false;
}
bool u_f_set(){
    for(int i=1;i<=n;i++)   //初始化fa
        fa[i]=i;
    bool cir=0;             //是否形成环
    for(int i=0;i<m1;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        if(!cir&&Union(u,v))    //如果形成环，只需输入，不操作
            cir=1;
    }
    return cir;
}
bool topo_sort(){
    for(int i=0;i<=n;i++)
        Mp[i].clear();
    memset(indeg,0,sizeof(indeg));
    memset(flag,0,sizeof(flag));    
    bool cir=0;                     //初始化
    for(int i=0;i<m2;i++){  
        int u,v,fu,fv;
        scanf("%d%d",&u,&v);
        if(cir==1)                  //如果已经有环，只需输入
            continue;
        fu=Find(u);
        fv=Find(v);
        if(fu==fv){                 //如果有向边两个端点在一个集合（缩点）中，必成环
            cir=1;
        }else{
            Mp[fu].push_back(fv);   //存有向边
            indeg[fv]++;            //该集合（缩点）入度加一
        }
    }
    if(cir==1){
        return 1;
    }else{
        queue<int>Q;
        while(!Q.empty())
            Q.pop();
        int cnt_c=0;
        for(int i=1;i<=n;i++){
            int i_f=Find(i);
            if(i_f==i){
                cnt_c++;            //记录所有集合（缩点）个数
            }
            if(indeg[i_f]==0&&flag[i_f]==0){    //该集合（缩点）入度为零，且未加入队列
                Q.push(i_f);
                flag[i_f]=1;
            }
        }
        int cnt=0;
        while(!Q.empty()){  //bfs_topo排序
            int u=Q.front();
            cnt++;          //记录拓扑排序排了多少个集合（缩点）
            Q.pop();
            for(int i=0;i<Mp[u].size();i++){
                int j=Mp[u][i];
                indeg[j]--;
                if(indeg[j]==0&&flag[j]==0){
                    Q.push(j);
                    flag[j]=1;
                }
            }
        }
        if(cnt_c==cnt){ //如果总的集合个数等于拓扑排序的集合个数，说明无环
            return false;
        }else{
            return true;
        }
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m1,&m2);
        if(u_f_set()){
            for(int i=0;i<m2;i++){
                int u,v;
                scanf("%d%d",&u,&v);
            }printf("YES
");
        }
        else{
            if(topo_sort()) printf("YES
");
            else printf("NO
");
        }
    }
}

/*

55
3 1 1
1 3
3 2
NO
4 2 2
1 2
2 3
4 3
4 1
NO
7 3 4
2 1
1 7
3 4
6 3
5 6
4 5
7 6
YES
4 1 3
4 1
3 2
4 3
4 1
YES
7 2 3
1 2
2 3
4 5
5 6
6 4
YES
9 4 4
1 2
1 7
3 4
8 9
7 6
5 6
4 5
6 3
YES
*/