Share my concise Union-Find solution-Java


  • 0
    S
    public class Solution {
        public int findCircleNum(int[][] M) {
            int n = M.length;
            int[] roots = new int[n];
            for (int i = 0; i < n; i++) roots[i] = i;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (M[i][j] == 1) {
                        int root1 = find(roots, i);
                        int root2 = find(roots, j);
                        if (root1 != root2) roots[root2] = root1;
                    }
                }
            }
            Set<Integer> set = new HashSet<>();
            for (int node : roots) set.add(find(roots, roots[node]));
            return set.size();
        }
        
        public int find(int[] roots, int id) {
            while (roots[id] != id) id = roots[id];
            return id;
        }
    }
    

Log in to reply
 

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