C++::data_structures::UnionFind

UnionFind.cpp

class UnionFind {
private:
  vector<int> p;
  vector<int> rank;

public:
    UnionFind(int n) {
        rank.assign(n, 0);
	p.resize(n);
	for (int i = 0; i < n; ++i) p[i] = i;
    }
    int findSet(int i) {
    	return p[i] == i ? i : p[i] = findSet(p[i]);
    }
    bool isSameSet(int i, int j) {
    	return findSet(i) == findSet(j);
    }
    void join(int i, int j) {
    	if (isSameSet(i, j)) return;
    	int u = findSet(i), v = findSet(j);
    	if (rank[u] > rank[v]) p[v] = u;
    	else {
    	    p[u] = v;
    	    if (rank[u] == rank[v]) ++rank[v];
    	}
    }
};