simple Java solution using union-find


  • 0
    D
    public int findCircleNum(int[][] M) {
            int len = M.length;
            int[] root = new int[len];
            int cnt = 0;
            for (int i = 0; i < len; i++) {
                root[i] = i;
            }
            for (int i = 0; i < len; i++) {
                for (int j = i + 1; j < len; j++) {
                    if (M[i][j] == 1) {
                        union(root, i, j);
                    }
                }
            }
            for (int i = 0; i < len; i++) {
                if (root[i] == i) cnt++;
            }
            return cnt;
            
        }
        // connect i and j if they are not connected by setting root[i] = j
        private void union(int[] root, int i, int j) {
            int _i = find(root, i);
            int _j = find(root, j);
            if (_i != _j) root[_i] = _j;
        }
        // root[idx] = idx if they are separate else find the parent
        private int find(int[] root, int idx) {
            if (root[idx] == idx) return idx;
            return find(root, root[idx]);
        }

Log in to reply
 

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