Union Find - JAVA


  • 0
    H
    class Solution {
        public int[] findRedundantConnection(int[][] edges) {
    
            Redundant_QuickUnion redundant_quickUnion = new Redundant_QuickUnion(edges);
            int[] result = null;
            for(int[] pair : edges){
                if(redundant_quickUnion.connected(pair[0], pair[1])){
                    result = pair;
                }else {
                    redundant_quickUnion.union(pair[0], pair[1]);
                }
            }
            return result;
        }
    }
    
    class Redundant_QuickUnion {
        private Map<Integer, Integer> map;
    
        public Redundant_QuickUnion(int[][] edges) {
            map = new HashMap<>();
        }
    
        public int find(int p) {
            while (map.containsKey(p) && p != map.get(p)) {
                p = map.get(p);  // chase parent's pointers until reach root
            }
            return p;
        }
    
        public boolean connected(int p, int q) {
            return find(p) == find(q);   // check if p and q have same root
        }
    
        public void union(int p, int q) {
            int i = find(p);
            int j = find(q);
            map.put(j, i);   // change root of p point to root of q
        }
    }
    

Log in to reply
 

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