并查集

struct DSU {
    vector<int> fa, rk;

    explicit DSU(int n) :fa(n + 1), rk(n + 1) {
        for (int i = 1;i <= n;i++)
            fa[i] = i;
    }

    void init(int n) {
        for (int i = 1;i <= n;i++)
            fa[i] = i, rk[i] = 0;
    }

    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

    bool same(int x, int y) { return find(x) == find(y); }

    void merge(int x, int y) {
        if (same(x, y)) return;
        int px = fa[x], py = fa[y];
        if (rk[px] > rk[py]) fa[py] = px;
        else if (rk[px] < rk[py]) fa[px] = py;
        else fa[px] = py, rk[py]++;
    }
};
///并查集（路径压缩+按秩合并），O(nα(n))，用于维护集合关系

带权并查集

template<class T>
struct DSU {
    vector<int> fa;
    vector<T> w;

    explicit DSU(int n) :fa(n + 1), w(n + 1, T::e()) {
        for (int i = 1;i <= n;i++)
            fa[i] = i;
    }

    void init(int n) {
        for (int i = 1;i <= n;i++)
            fa[i] = i, w[i] = T::e();
    }

    int find(int x) {
        if (fa[x] == x) return x;
        int pre = fa[x];
        fa[x] = find(fa[x]);
        w[x] = w[x] + w[pre];
        return fa[x];
    }

    bool same(int x, int y) { return find(x) == find(y); }

    bool merge(int x, int y, T _w) {
        if (same(x, y)) return w[x] + -w[y] == _w;
        int px = fa[x], py = fa[y];
        fa[px] = py;
        w[px] = -w[x] + _w + w[y];
        return true;
    }//注意方向，x合并到y
};
///带权并查集（路径压缩），O(nlogn)，用于维护集合带权关系

struct T {
    double rate;
    static T e() { return T{ 1.0 }; }
    friend T operator+(const T &a, const T &b) { return T{ a.rate * b.rate }; }
    friend T operator-(const T &a) { return T{ 1 / a.rate }; }
    friend bool operator==(const T &a, const T &b) { return abs(a.rate - b.rate) < 1e-6; }
};
///变量封装在一个类里，需要重载加号，负号，逻辑等于号