Java, simplified Union-Find


  • 0
    B
    public class Solution {
        public int findCircleNum(int[][] M) {
            int num = M.length;
            int[] friends = new int [num];
            for (int i = 0; i < num; i++) {
                friends[i] = i;
            }
            
            for (int i = 0; i < num; i++) {
                for (int j = 0; j < num; j++) {
                    if (M[i][j] == 0 || i <= j) continue;
                    
                    int rootI = findRoot(friends, i);
                    int rootJ = findRoot(friends, j);
                    friends[Math.max(rootI, rootJ)] = friends[Math.min(rootI, rootJ)];
                }
            }
            
            Set<Integer> set = new HashSet<Integer>();
            
            for (int i = 0; i < num; i++) {
                int root = findRoot(friends, i);
                if (set.contains(root))
                    continue;
                
                set.add(root);
            }
            
            return set.size();
        }
    
        private int findRoot(int[] friends, int p) {
            int root = friends[p];
            while(root != friends[root]) {
                friends[root] = friends[friends[root]];
                root = friends[root];
            }
            return root;
        }
    }
    

Log in to reply
 

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