Concise Java Union-Find Solution, O(N) space


  • 0
    public class Solution {
        public int findCircleNum(int[][] M) {
            int[] parent = new int[M.length]; //index of the first student who transfers the friendship to the ith student
            for (int i = 0; i < M.length; ++i) parent[i] = i; //intialization
            int count = M.length;
            for (int row = 0; row < M.length; ++row) {
                for (int col = row + 1; col < M.length; ++col) {
                    if (M[row][col] == 0) continue;
                    int rParent = find(parent, row);
                    int cParent = find(parent, col);
                    if (rParent == cParent) continue;
                    parent[cParent] = row; //union
                    --count;
                }
            }
            return count;
        }
        
        private int find(int[] parent, int index) {
            while (parent[index] != index) index = parent[index];
            return index;
        }
    }
    

Log in to reply
 

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