C++ union find with path compression O(N) time O(N) space


  • 0
    C

    There are two cases that a directed graph is not a tree
    (1). a node has > 1 parent
    (2). there is a cycle
    we can handle this two cases separately. To handle (2), we can achieve it using multi ways: DFS, BFS, and union find. Here we use union find. To handle (1), we need a data structure to track every node's parent, and unordered_map is very handy to do that. That's why you see two hashmaps used here, "parent" and "root". "root" is for tracking the root/representation of the connected components as in standard union find handling. "parent" is just for tracking parent of each node.

    class Solution {
    public:
        unordered_map<int,int> parent, root;
        int find(int x) {
            if(!root.count(x)) return root[x] = x; 
            int y = x;
            while(x != root[x]) {
                x = root[x];
            }
            while(root[y] != x){
                int tmp = root[y];
                root[y] = x;
                y = tmp;
            }
            return x;
        }
        void merge(int a, int b) {
            int fa = find(a), fb = find(b);
            if(fa != fb) {
                root[fa] = fb;
            }
        }
        
        vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
            vector<int> ans;
            for(auto e : edges) {
                // handle parent 
                if(parent.count(e[1])) {
                    ans = e;
                    return ans;
                }
                parent[e[1]] = e[0];
                
                // handle cycle
                int fa = find(e[0]), fb = find(e[1]);
                if(fa == fb) ans = e; // detect a cycle
                else merge(e[0], e[1]);
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.