python/TangDou/AcWing/EulerPath/LianTongXing/BCJ.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; // 图的最大点数量
/**
 共提供两组数据，样例1为不连通用例，样例2为连通用例

 样例1：不连通，5号结点为独立的
 5 4
 1 2
 2 3
 3 4
 1 4

 样例2：连通，不存在独立结点
 5 4
 1 2
 2 3
 3 4
 1 5

 检测各种算法是否能准确获取结果
 */
int n;    // n个人
int m;    // m个亲戚
int x, y; // 输入两个人之间的关系
int p[N]; // 并查集数组
// 要深入理解这个递归并压缩的过程
int find(int x) {
    if (p[x] != x)         // 如果x不是族长,递归找父亲,副产品就是找回的结果更新掉自己的家族信息。
        p[x] = find(p[x]); // 非常经典的更新,路径压缩大法！
    // 返回族长是谁
    return p[x];
}

int cnt;

int main() {
#ifndef ONLINE_JUDGE
    // freopen("in1.in", "r", stdin);
    freopen("in2.in", "r", stdin);
#endif
    // n个人员，m个关系
    cin >> n >> m;
    // 并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i; // 自己是自己的老大
    // 录入m种关系,使用并查集来判断图的连通性
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        // 加入并查集
        int px = find(x), py = find(y);
        if (px != py) p[px] = py;
    }
    // 图已经搭好了，接下来看它们根节点是否相同，如只有一个相同的根节点，则说明是一个连通图
    for (int i = 1; i <= n; i++)
        if (p[i] == i) cnt++;

    if (cnt == 1)
        printf("图是连通的\n");
    else
        printf("图不是连通的\n");
    return 0;
}