HDU 1272 小希的迷宫

一道很简单的并查集

建模之后就是判断一个无向图有没有环就行了

注意没有任何数据的时候是要输出一个“yes”，如果输入两个相同的点的时候，应该不判断

贴一下代码先

#include <stdio.h>
#include <string.h>

#define maxn 100100
int fa[maxn];

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

void union_set(int x ,int y) {
    fa[x] = y;
}

bool fail = false;

int vis[maxn];

void init(){
    fail = false;
    for(int i=0;i<maxn;i++) fa[i] = i;
    memset(vis ,0 , sizeof(vis));
}
int a,b,u,v;

int main(){
    while(scanf("%d %d",&a,&b),a+b>=0){
        if(a+b == 0) {
            puts("Yes");
            continue;
        }
        init();
        fail = false;
        if(a!=b){ 
            u = find(a) , v = find(b);
            union_set(u,v);
            vis[a]=1;vis[b]=1;
        }
        while(scanf("%d %d",&a,&b),a+b){
            u = find(a) , v = find(b);
            vis[a]=vis[b]=1;
            if(a==b) continue;
            if(u != v){
                union_set(u,v);
            }
            else{
                fail = true;
            }
        }
        int cnt = 0 , mk , st;
        
        for(int i=1;i<maxn;i++){
            if(vis[i] && fa[i] == i){
                cnt++;
            }
        }
        if(!fail) fail = cnt == 1 ? false : true;
        if(fail) puts("No");
        else puts("Yes");
    }
    return 0;
}
/*
1 1 1 2 3 1 3 3
0 0

*/