python/TangDou/XiTi/1416.cpp

#include <bits/stdc++.h>

using namespace std;

#pragma region 并查集模板
int p[101]; //存储元素的父节点
int Rank[101]; //存储树的高度(秩)
//建立并查集
void Build(int n) {
    for (int i = 1; i <= n; ++i) {
        p[i] = i; //父结点是元素自身
    }
}

//查找根结点//路径压缩
int Find(int x) {
    if (p[x] != x)
        p[x] = Find(p[x]);
    return p[x];
}

//按秩合并集合
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (Rank[x] < Rank[y]) p[x] = y;
    else {
        p[y] = x;
        if (Rank[y] == Rank[x]) Rank[x]++;
    }
}

#pragma endregion 并查集模板

int main() {
    //输入+输出重定向
    freopen("../1416.txt", "r", stdin);

    int n, m;
    cin >> n >> m;
    //建立并查集
    Build(n);

    //合并集合
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        //国家的较量首先从势力上进行比较，吞并国家多的能打赢吞并国家少的。
        //如果两个国家的吞并的国家相同，就根据国家头目的编号来判断，我们假设编号大的国家能打得过编号小的国家。
        //谁来合并谁？
        int u1 = Find(u);
        int uCount = 0;

        int v1 = Find(v);
        int vCount = 0;

        for (int j = 0; j < 101; ++j) {
            if (p[j] == u1) uCount++;
            if (p[j] == v1) vCount++;
        }

        if (uCount > vCount) {
            Union(u1, v1);
        }
        if (uCount < vCount) {
            Union(v1, u1);
        }
        if (uCount == vCount) {
            if (u > v) Union(u1, v1);
            else Union(v1, u1);
        }
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int s;
        cin >> s;
        int p = Find(s);
        //计算有多少个
        int count = 0;
        for (int j = 1; j <= n; ++j) {
            if (Find(j) == p) count++;
        }
        cout << p << " " << count << endl;
    }

    //关闭文件
    fclose(stdin);
    return 0;
}