因为要支持撤销操作, 所以没法路径压缩, 只能按秩合并, 这里的秩为深度.

用一个栈来记录每次 bind 操作之前的状态, undo 的时候直接从栈中取即可.

class UDSU {
public:
    std::vector<int> f, size;
    std::stack<std::array<int, 2>> sta;
    UDSU(std::size_t size) : f(size + 1), size(size + 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    int root(int u) {
        return f[u] == u ? u : root(f[u]);
    }
    void bind(int u, int v) {
        u = root(u), v = root(v);
        if (size[u] > size[v])
            std::swap(u, v);
        sta.push({u, size[v]});
        f[u] = v;
        if (size[u] == size[v])
            size[v]++;
    }
    void undo() {
        auto [u, sizev] = sta.top();
        sta.pop();
        size[f[u]] = sizev, f[u] = u;
    }
};