Concise Java Solution, O(n^2) time, O(n) space, while n is the number of students.


  • 0
    F
    public class Solution 
        public int findCircleNum(int[][] M) {
            if (M.length == 0) {
                return (0);
            }
            
            int n = M.length;
            int res = 0;
            boolean[] visited = new boolean[n];
            
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    res++;
                    helper(M, visited, i);
                }
            }
            
            return (res);
        }
        
        void helper(int[][] M, boolean[] visited, int p) {
            if (visited[p]) {
                return;
            }
            
            int n = M.length;
            
            visited[p] = true;
            for (int i = 0; i < n; i++) {
                if (M[p][i] == 1) {
                    helper(M, visited, i);
                }
            }
        }
    }
    

Log in to reply
 

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