HDU1272 小希的迷宫(并查集)

题目链接。

解题报告：

首先1.题目上说的房间的编号至少为1，也就是说，当输入只0 0时，要输出Yes。

2.在连通两个房间时，如果发现已经间接地连通了，那么结果便是No.

3.要保证给出的所有房间之间都必须连通，否则便是No。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100010
int p[MAXN], ans, v[MAXN], n, flag;
void Init(){
    n = 0;
    flag = 1;
    ans = 0;
    memset(v, 0, sizeof(v));
    int i;
    for(i=1; i<=MAXN; i++) p[i] = i;
}
int find(int x){
    int r = x;
    while(p[r] != r){
        r = p[r];
    }
    return (x = p[r]);  //压缩路径
}
int merge(int a, int b){
    a = find(a); b=find(b);
    if(a == b) return 0;
    p[a] = b;
    ans++;
    return 1;
}
int main(){
    int a, b;
    Init();
    while(scanf("%d%d", &a, &b) == 2){
        if(a == -1 && b == -1) break;
        else if(a == 0 && b == 0){
            if(flag && n != 0 && ans != n-1) flag = 0;
            if(flag) printf("Yes\n");
            else printf("No\n");
            Init();
            continue;
        }
        if(!v[a]){n++; v[a] = 1;}
        if(!v[b]){n++; v[b] = 1;}
        if(flag)
            if(!merge(a, b))
                flag = 0;
    }
    return 0;
}