并查集做法

· · 题解

题意：

给你一个有向图，要你判定这个有向图是不是树。

思路：

使用并查集，每次把入点合并到出点，最后，一棵树上的所有结点一定在一个连通块内。

在此过程中，有两种非法情况：

  1. 两个端点已经在同一连通块内，则说明存在环；

  2. 入点已经在另外一个连通块（非自身），则说明一个点被指向 \operatorname{2} 次，一定不是树。

最后判断连通块数量是否为 \operatorname{1} ；如果不是，说明是森林。

以上操作都是并查集的最基础操作，相信我们的读者都能独立做到。

将点数和边数的最大值设为 \operatorname{n} ，把反阿克曼函数视为 \operatorname{1} ，时间复杂度为 \operatorname{O(nlog(n))} 。

注意事项 ：

  1. 为了通过 uDEBUG 上的超大数据，必须开 map 离散化，实际上 UVA 和 HDU 都没有卡这个；

  2. 没有任何节点也算是树；

  3. UVA 上 没有第二种非法情况，而 HDU 上有。

代码：

抄袭可耻，自过光荣。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
const int N=5e6+10;
map<int,int> q;
int n,cnt,blocnt,fa[N];
struct node{
    int l,r;
}edge[N];
bool st[N];
int find(int x){
    if(fa[x]==x){
        return x;
    }
    return fa[x]=find(fa[x]);
}
void hb(int x,int y){
    fa[y]=x;
}
int main(){
    int x,y;
    while(scanf("%d%d",&x,&y)&&x>=0&&y>=0){
        ++n,cnt=1,blocnt=0;
        q.clear();
        if(x==0&&y==0){
            printf("Case %d is a tree.\n",n);
            continue;
        }
        if(!q[x]){
            blocnt++;
            q[x]=blocnt;
        }
        if(!q[y]){
            blocnt++;
            q[y]=blocnt;
        }
        edge[1].l=q[x],edge[1].r=q[y];
        while(scanf("%d%d",&x,&y)&&x!=0&&y!=0){
            if(!q[x]){
                blocnt++;
                q[x]=blocnt;
            }
            if(!q[y]){
                blocnt++;
                q[y]=blocnt;
            }
            edge[++cnt].l=q[x],edge[cnt].r=q[y];
        }
        for(int i=1;i<=blocnt;i++){
            fa[i]=i;
            st[i]=false;
        }
        bool flag=true;
        for(int i=1;i<=cnt;i++){
            int fx=find(edge[i].l),fy=find(edge[i].r);
            if(fx==fy){
                flag=false;
                break;
            }
            else if(fy!=edge[i].r){
                flag=false;
                break;
            }
            else{
                hb(fx,fy);
                blocnt--;
            }
        }
        if(flag==true&&blocnt==1){
            printf("Case %d is a tree.\n",n);
        }
        else{
            printf("Case %d is not a tree.\n",n);
        }
    }
}