模板 - 数据结构 - 并查集

Codeforces Round #600 里面有用到这个，但是真的重新打浪费时间。

不需要什么按秩合并，浪费空间多此一举，让那个合并的常数大了不少。但是循环还是有必要的，比递归快很多。

真香，要加也不是不可以……也没慢多少……

struct DisjointSetUnion {
    static const int MAXN = 200000;
    int n, fa[MAXN + 5], rnk[MAXN + 5];
 
    void Init(int _n) {
        n = _n;
        for(int i = 1; i <= n; i++) {
            fa[i] = i;
            rnk[i] = 1;
            maxid[i] = i;
        }
    }
 
    int Find(int u) {
        int r = fa[u];
        while(fa[r] != r)
            r = fa[r];
        int t;
        while(fa[u] != r) {
            t = fa[u];
            fa[u] = r;
            u = t;
        }
        return r;
    }
 
    bool Merge(int u, int v) {
        u = Find(u), v = Find(v);
        if(u == v)
            return false;
        else {
            if(rnk[u] < rnk[v])
                swap(u, v);
            fa[v] = u;
            rnk[u] += rnk[v];
            return true;
        }
    }
} dsu;

模板 - 数据结构 - 并查集

原文：https://www.cnblogs.com/KisekiPurin2019/p/11876274.html