Union Find algorithm for disjoint set (并查集算法）

Mainly need to implement two functions `Union` and `Find`, then it is pretty straight forward to use these two functions to get the number of clusters or find the redundant edges etc.


 (1)     684  Redundant Connection  
 
class Solution {
public:
    vector<int> parent;
    vector<int> rank;
    int Find(int x) {
        if (x != parent[x])
            // return Find(parent[x]); // Non optimized version
            parent[x] = Find(parent[x]); // Optimized version. Flatten the tree while finding


     
        // Please note you cannot just return x instead, assuming x is always equal to parent[x].
        // It is possible that x == parent[x] in the first recursion. But the recursion call return
        // value will update the global varible parent, after that x is no longer equal to parent[x]
        // we want to always return the latest parent of the cluster (not the old not updated x value)
        return parent[x];
    }
   
    // Optimized union, always append smaller rank nodes to larger rank nodes
    void Union(int x, int y) {
        int parentX = Find(x);
        int parentY = Find(y);
        if (rank[parentX] > rank[parentY])
            parent[parentY] = parentX;
        else if (rank[parentX] < rank[parentY])
            parent[parentX] = parentY;
        else {
            parent[parentY] = parentX;
            rank[parentX]++;
        }
    }
 
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        rank = vector<int>(edges.size() + 1, 0);
        parent = vector<int>(edges.size() + 1);
        int N = edges.size();
        for (int i = 1; i <= N; ++i) {
            parent[i] = i; // every node points to itself initially
        }
     
        for (const auto& edge : edges) {
            if (Find(edge[0]) == Find(edge[1])) // in the same cluster already, redundant edge
                return edge;
            else
                Union(edge[0], edge[1]); // union operation
        }
     
        return {};
    }
};



（2） 547  Friend Circles   

class Solution {
public:
    vector<int> parent;
    vector<int> rank;
    int Find(int x) {
        if (x != parent[x])
            parent[x] = Find(parent[x]);
     
        return parent[x];
    }
 
    /* non optimized Union
    void Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);
        parent[px] = py;
    } */
 
    // Optimized Union
    void Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);
     
        if (rank[px] > rank[py])
            parent[py] = px;
        else if (rank[px] < rank[py])
            parent[px] = py;
        else {
            parent[px] = py;
            rank[py]++;
        }
    }
 
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        rank = vector<int>(n, 0);
        parent = vector<int>(n);
        for(int i = 0; i < n; ++i)
            parent[i] = i;
     
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (M[i][j] == 1)
                    Union(i, j);
            }
        }
     
        unordered_set<int> circles;
        for(int i = 0; i < n; ++i) {
            // Note this Find is still necessary, since otherwise, it is not completely flatted,
            // you may have a node that has grandparent. e.g:
            // 1 0 0 1
            // 0 1 1 0
            // 0 1 1 1
            // 1 0 1 1
            // After this Find in the loop, all nodes don't have grandparent. Each cluster has at
            // a height of at most 2, the root  number is equal to the cluster numbers.
            circles.insert(Find(i));
        }
     
        return circles.size();
    }
};




(3)   737  Sentence Similarity II  

class Solution {
public:
    vector<int> parent;
    vector<int> rank;
    int Find(int x) {
        if (x != parent[x])
            parent[x] = Find(parent[x]);
       
        return parent[x];
    }
   
   
    // Optimized Union
    void Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);
       
        if (rank[px] > rank[py])
            parent[py] = px;
        else if (rank[px] < rank[py])
            parent[px] = py;
        else {
            parent[px] = py;
            rank[py]++;
        }
    }
   
   
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
        if (words1.size() != words2.size())
            return false;
        int n = pairs.size() * 2;
        rank = vector<int>(n, 0);
        parent = vector<int>(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
       
        unordered_map<string, int> indices; // string to index
        int size = words1.size();
        for (const auto& pair : pairs) {
            int u = getIndex(pair.first, indices, true);
            int v = getIndex(pair.second, indices, true);
            Union(u, v);
        }
       
        for (int i = 0; i < size; ++i) {
            if (words1[i] == words2[i])
                continue;
            int u = getIndex(words1[i], indices);
            int v = getIndex(words2[i], indices);
            if (u < 0 || v < 0)
                return false;
            if (Find(u) != Find(v))
                return false;
        }
       
        return true;
    }
   
    private:
    // map string to int
    int getIndex(const string& word, unordered_map<string, int> &indices, bool created = false) {
        auto it = indices.find(word);
        if (it == indices.end()) {
            if (!created)
                return INT_MIN;
            int index = indices.size();
            indices.emplace(word, index);
            return index;
        }
       
        return it->second;
    }

};