小希的迷宫

题目描述

上次Gardon的迷宫城堡小希玩了很久，现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

图片说明

分析

目的很简单，其实就是用并查集判断给定的图是否是无向边的一棵树，所以只需要判断是否用重边和环就行了，所以对于给定的边，逐步join，如果遇到还没join之前某条边时，发现两个结点已经合并了，那就不是树，肯定有环。如果没有环，再判断一下是否联通，只需要看并查集fa[]数组中，每个结点的是不是连接到根结点上就可以了

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;
int id[maxn],tail;
int fa[maxn];
void init(){
    tail = 1;
    for(int i = 1;i<=100010;i++) fa[i] = i;
}

int find(int x){
    if(x!=fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
    }
}
int main(){
    int x,y;
    while(scanf("%d%d",&x,&y)){
        if(x == 0 && y == 0) {
            puts("Yes");
            continue;
        }
        init();
        bool ok = true;
        if(x == -1 && y == -1)break;
        do{
            id[tail++] = x,id[tail++] = y;
            if(find(x) != find(y)){
                join(x,y);
            }else{
                ok = false;
            }
        }while(scanf("%d%d",&x,&y) && !(x == 0 && y == 0));
        if(!ok) puts("No");
        else{
            for(int i = 1;i<tail;i++) find(id[i]); //压缩路径
            int h = fa[id[1]];
            for(int i = 1;i<tail;i++){
                if(find(id[i]) != h) {
                    ok = false;
                }
            }
            if(!ok) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}