并查集

涉及集合之间的关系，核心是每个元素最终都将唯一指向某个自旋元素，统计这样的元素数目以及它们出现的次数，即可得到每个集合的大小。需要注意的是初始时每个元素并非自旋，可以在查找其父节点而不可得的时候将其设置为自旋，当使用秩时，只有自旋节点的秩是有价值的，也可以在第一次查找到自旋节点时设置。

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int, int> fa; // fa[first] = second;
int find(int x) {
    if (fa.find(x) == fa.end()) {  // 即不指向任何节点的末端
        fa[x] = x;  // 将其设置为自旋
        return x;
    } else {
        if (fa[x] == x) {
            return x;
        } else {
            fa[x] = find(fa[x]);
            return fa[x];  // 返回当前的末端节点
        }
    }
}

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

int main(){
    int T;
    cin >> T;
    while (T) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            merge(x, y);
        }
        unordered_map<int, int> fa_count;
        int ans = 0;
        for (auto it = fa.begin(); it != fa.end(); ++it) {
            int father = find(it->first);
            ++fa_count[father];
            ans = max(ans, fa_count[father]);
        }
        cout << ans << endl;
        fa.clear();

        --T; // 如何按秩排序
    }
}