python/TangDou/AcWing/CheckCircle/HDU1272【并查集+枚举】.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 100500;

int n, m;         // n个顶点，m条边
bool flag = true; //默认是合格的，如果有环是false,不连通也是false
//每组数据，是否符合要求:1、任意两点间道路唯一，2、需要是连通的
bool st[N]; //节点是不是出现过

//最简并查集
int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); //路径压缩
    return p[x];
}
//合并集合
bool join(int a, int b) {
    if (find(a) == find(b)) return false;
    p[find(a)] = find(b);
    return true;
}

// 初始化各种状态数组和标识数据
void init() {
    flag = true;
    //初始化并查集
    for (int i = 0; i < N; i++) p[i] = i;
    //清空状态数组
    memset(st, 0, sizeof st);
}

int main() {
    int a, b;
    //初始化
    init();
    while (~scanf("%d%d", &a, &b), ~a && ~b) {
        if (a && b) {               //一组数据输入进行中
            st[a] = st[b] = true;   //标识a,b两个点走过了
            if (!join(a, b))        //如果两个点在一个集合中，说明有重复路线出现~
                flag = false;        //标记已经不合法
        } else {
            //单组数据输入结束
            //如果没有检查到环，才有资格检查是不是连通
            if (flag) {
                int cnt = 0;
                for (int i = 1; i < N; i++) {
                    if (st[i] && find(i) == i) cnt++; //判断根节点cnt数目
                    if (cnt > 1) {
                        flag = false;
                        break;
                    }
                }
            }
            //检查通过
            flag ? puts("Yes") : puts("No");

            //清空准备下一次输入
            init();
        }
    }
    return 0;
}