Union Find

Disjoint-set data structure
Union Find

// Minimum Spanning Tree
// Kruskal's algorithm
// implemented with disjoint-set data structure
// KRUSKAL(G):
// 1 A = ∅
// 2 foreach v ∈ G.V:
// 3    MAKE-SET(v)
// 4 foreach (u, v) in G.E ordered by weight(u, v), increasing:
// 5    if FIND-SET(u) ≠ FIND-SET(v):
// 6       A = A ∪ {(u, v)}
// 7       UNION(u, v)
// 8 return A
vector<int> parent(n, -1);
int find(vector<int>& parent, int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}
void Union(vector<int>& parent, int i, int j, int& circles) {
    // can't use the function name union(), union is a c++ keyword
    int x = find(parent, i);
    int y = find(parent, j);
    if (x != y) {
        parent[x] = y;
    }
}

// Friend Circles
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        const int n = M.size();
        int circles = n;
        vector<int> parent(n, -1);
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (M[i][j])
                    Union(parent, i, j, circles);
            }
        }
        return circles;
    }
    
    int find(vector<int>& parent, int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }
    
    void Union(vector<int>& parent, int i, int j, int& circles) {
        // can't use the function name union(), union is a c++ keyword
        int x = find(parent, i);
        int y = find(parent, j);
        if (x != y) {
            parent[x] = y;
            circles--;
        }
    }
};

// Accounts Merge
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string>> res;
        unordered_map<string, int> cache;
        vector<int> parent(accounts.size(), -1), rank(accounts.size(), 0);
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 1; j < accounts[i].size(); j++) {
                if (cache.find(accounts[i][j]) == cache.end())
                    cache[accounts[i][j]] = i;
                else
                    Union(parent, rank, cache[accounts[i][j]], i);
            }
        }
        unordered_map<int, int> idCache;
        unordered_set<string> stringCache;
        int k = 0;
        for (int i = 0; i < accounts.size(); i++) {
            int id = find(parent, i);
            if (idCache.find(id) == idCache.end()) {
                vector<string> acc;
                acc.push_back(accounts[i][0]);
                idCache[id] = k;
                for (int j = 1; j < accounts[i].size(); j++) {
                    if (stringCache.find(accounts[i][j]) == stringCache.end()) {
                        stringCache.insert(accounts[i][j]);
                        acc.push_back(accounts[i][j]);
                    }
                }
                res.push_back(acc);
                k++;
            } else {
                id = idCache[id];
                for (int j = 1; j < accounts[i].size(); j++) {
                    if (stringCache.find(accounts[i][j]) == stringCache.end()) {
                        stringCache.insert(accounts[i][j]);
                        res[id].push_back(accounts[i][j]);
                    }
                }
            }
        }
        for (int i = 0; i < res.size(); i++)
            sort(res[i].begin(), res[i].end());
        return res;
    }
    
    int find(vector<int>& parent, int i) {
        if (parent[i] == -1)
            return i;
        parent[i] = find(parent, parent[i]); // uses path compression technique
        return parent[i];
    }
    
    void Union(vector<int>& parent, vector<int>& rank, int i, int j) {
        // can't use the function name union(), union is a c++ keyword
        int x = find(parent, i);
        int y = find(parent, j);
        if (x != y) {
            if (rank[x] < rank[y])
                parent[x] = y;
            else if (rank[x] > rank[y])
                parent[y] = x;
            else {
                parent[x] = y;
                rank[y]++;
            }
        }
    }
};