Union Find

[-] Collapse

struct Union_Find{
    int components;
    vector<int> parent, rank;
    Union_Find(int n):parent(n),rank(n), components(n){
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int u){
        if (u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    bool merge(int u, int v){
        u = find(u); v = find(v);
        if (u == v) return false;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) ++rank[v];
        components--;
        return true;
    }
};