AC Java Union-Find solution


  • 161
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            // initialize n isolated islands
            int[] nums = new int[n];
            Arrays.fill(nums, -1);
            
            // perform union find
            for (int i = 0; i < edges.length; i++) {
                int x = find(nums, edges[i][0]);
                int y = find(nums, edges[i][1]);
                
                // if two vertices happen to be in the same set
                // then there's a cycle
                if (x == y) return false;
                
                // union
                nums[x] = y;
            }
            
            return edges.length == n - 1;
        }
        
        int find(int nums[], int i) {
            if (nums[i] == -1) return i;
            return find(nums, nums[i]);
        }
    }

  • 0
    C

    Really elegant & concise implement to use an array to represent union relationship and use DFS to construct and check it.


  • 0
    A

    Excellent! Thanks!


  • 6
    A

    The solution is excellent, but I also wander the complexity of this solution. According to my inference, the worst case time complexity is O(n^2) when each node has only one child in a tree. The best case time complexity is O(n) when the height of the tree is 2.


  • 2
    S

    Can you guide me to the resources of knowledge point which related to the "find function" you defined? I feel it is not easy to understand and impossible to come up this idea to find which is the set a number belongs to?


  • 8
    A

    Hi Steven,

    There is good resource for learning this classic algorithm:
    https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

    I think there may be a little obstacle in understanding Jeantimex's solution of tracing back a node's set number through DFS. I have made following analysis, hope it helps.

    Suppose we have already known "node_m" in the set "0" and we update the union array through following way,
    int x = findUnion(union, edge[0]);
    int y = findUnion(union, edge[1]);
    union[y] = x;

    Two possible cases for a new edge.
    Case 1: [node_m node_n]
    Case 2: [node_n node_m]

    For case 1:
    x = findUnion(union, node_m) = 0;
    y = findUnion(union, node_n) = node_n;
    union[node_n] = 0;
    When we use DFS method, we can trace node_n's set number is 0.

    For case 2:
    x = findUnion(union, node_n) = node_n;
    y = findUnion(union, node_m) = 0;
    union[0] = node_n
    When we use DFS method, we can trace all explored nodes in the set back to set node_n.


  • 1

    Hi Steven, for detailed explanation, I recommend this article from geeksforgeeks: http://www.geeksforgeeks.org/union-find/


  • 3

    Hi Airwindow, let's say the graph has V vertices and E edges, the find( ) function takes O(V) time because in the worst case it has to go through all the vertices, and from outside we loop through all the edges, so the time complexity should be O(V*E).


  • 0
    A

    Thanks! Your answer is more accurate. I should not suppose |E| = |V| - 1.


  • 0
    X

    Is it right to resolve it by:
    https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg

    
    public boolean validTree(int n, int[][] edges) {
         final Set<Integer> set = new HashSet<>();
            for (int i = 0, len = edges.length; i < len; i++) {
                if (set.add(edges[i][0]) == false) {
                    set.remove(edges[i][0]);
                }
                if (set.add(edges[i][1]) == false) {
                    set.remove(edges[i][1]);
                }
                if (set.size() == 0) {
                    return false;
                }
            }
            return edges.length == n - 1;
    }
    

  • 0
    Z

    The algorithm can be O(N + MlogN) with little modification


  • 0
    Z

    Your "find" method should also return length, so the time can be O(N+MlogN). Check Princeton's page mentioned by airwindow. GeeksForGeeks's impl is not good enough.


  • 11
    Y

    Below is just a more complete(verbose) version.
    But I still prefer @jeantimex's solution. It's better for interview.

    First define the Union-Find class, with some optimization: weighted quick-union and path compression. This will greatly reduce the time complexity of union and find operations. See the reference link below. Read thru it. It's very useful.
    Then solve the problem is very straight-forward.
    reference: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

    class UF {
    	// union-find, bfs
    	int N;
    	int[] id;
    	int[] sz;
    	int segments;
    	public UF(int n){
    		N = n;
    		segments = n;
    		id = new int[N];
    	    sz = new int[N];
    		for(int i=0; i<N; i++){
    			id[i] = i;
    			sz[i] = 1;
    		}
    	}	
    	public int root(int i) {
    		while(i!=id[i]){
    			id[i] = id[id[i]]; // path compression
    			i = id[i];
    		}
    		return i;
    	}
    	public void connect(int p, int q){
    		int i = root(p);
    		int j = root(q);
    		if(i == j) return;
    		if(sz[i]<sz[j]) { // if-else: weighted quick-union
    			id[i] = j;
    			sz[j] += sz[i];
    		}
    		else if(sz[i]>sz[j]) {
    			id[j] = i;
    			sz[i] += sz[j];
    		}
    		else {
    			id[j] = i;
    			sz[i] += sz[j];
    		}
    		segments--;
    	}
    	public boolean connected(int p, int q) {
    		if(root(p)==root(q)){
    			return true;
    		}
    		return false;
    	}
    }
    public class Solution {
    	public boolean validTree(int n, int[][] edges) {
    		UF uf = new UF(n);
    		int M = edges.length;
    		for(int i=0; i<M; i++){
    			int p = edges[i][0], q = edges[i][1];
    			if(uf.root(p)==uf.root(q)){
    				return false;
    			}
    			uf.connect(p, q);
    		}
    		
    		if (uf.segments!=1){
    			return false;
    		}
    		
    		return true;
    	}
    }

  • 0
    J

    The hashset solution by li.haiyang.18 is awesome!


  • 0
    R

    Great solution! But I think you do no need to use this function "Arrays.fill(nums, -1);", only modify the function find "if (nums[i] == -1) return i;" to "if (nums[i] == 0) return i;" it is still work


  • 0
    R

    Great solution! But I think you do no need to use this function "Arrays.fill(nums, -1);", only modify the function find "if (nums[i] == -1) return i;" to "if (nums[i] == 0) return i;" it is still work


  • 1
    H

    set solution is not correct for case: n = 5, [0 1], [1 2], [2 5], [2, 0]


  • 3
    S

    Great solution. I think you can check edges.length == n - 1 at the beginning before starting union find.


  • 0
    O

    share my solution. I "randomized" the merge of union sets

    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            if (edges.length != n - 1) return false;
            UnionSet us = new UnionSet(n);
            for (int[] edge : edges)
                if (!us.merge(edge[0], edge[1])) return false;
            return true;
        }
        
        private class UnionSet {
            private int[] p;
            
            public UnionSet(int n) {
                p = new int[n];
                for (int i = 0; i < n; i++) p[i] = i;
            }
            
            public int find(int i) {
                if (p[i] != i) p[i] = find(p[i]);
                return p[i];
            }
            
            public boolean merge(int i, int j) {
                int a = find(i), b = find(j);
                if (a == b) return false;
                if ((a & 1) == 0) p[a] = b; else p[b] = a; // randomize the merge
                return true;
            }
        }
    }

  • 0
    F

    agree. but use the connected methode you created:
    for(int[] edge:edges){
    int p=edge[0];
    int q=edge[1];
    if(uf.connected(p,q)) return false;
    uf.unite(p,q);
    }


Log in to reply
 

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