Java Find Union Solution


  • 0
    S
    public class Solution {
            public int findCircleNum(int[][] M) {
                int len = M.length;
    	    int[] branch = new int[len];
    	    for(int i=0; i<len; i++)
    		branch[i]=i;
    		
    	    for(int i=0; i<len; i++){
    		for(int j=i+1; j<len; j++){
    		    if(M[i][j]==1){
    			int ibranch = find(i, branch);
    			int jbranch = find(j, branch);
    			//Union two trees
    			branch[jbranch]=ibranch;
    		    }
    		}
    	    }
    
    	    //find number of unconnected graphs
    	    Set<Integer> numCircle = new HashSet<>();
    	    for(int i=0; i<len; i++){
    	        int x = find(i, branch);
    		numCircle.add(x);
    	    }
    		
    	    return numCircle.size();
    	}
    	
    	private int find(int x, int[] branch){
    	    if(branch[x]==x)
    		return x;
    	    //path compressing
    	    branch[x]=find(branch[x], branch);
    	    return branch[x];
    	}
    }

Log in to reply
 

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