java union find


  • 0
    public class Solution {
    	public int findCircleNum(int[][] M) {
    		int[] circle = new int[M.length];
    		Arrays.fill(circle, -1);
    		for (int i = 0; i < M.length; i++) {
    			for (int j = i + 1; j < M[i].length; j++) {
    				if (M[i][j] == 1) {
    					int x = findroot(circle, i);
    					int y = findroot(circle, j);
    					if(x != y){
    						circle[x] = y;
    					}
    				}
    			}
    		}
    		int result = 0;
    		for (int i = 0; i < circle.length; i++) {
    			System.out.println(circle[i]);
    			if (circle[i] == -1) {
    				result++;
    			}
    		}
    		return result;
    	}
    	
    	private int findroot(int[] nums, int x){
    		if(nums[x] == -1){
    			return x;
    		}
    		int temp = findroot(nums, nums[x]);
    		nums[x] = temp;
    		return temp;
    	}
    }
    

Log in to reply
 

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