[JAVA] We can use visited array as memoization / T <= O(N^2), S : O(N)


  • 0
    J
    class Solution {
        public int findCircleNum(int[][] M) {
            int n = M.length;
            int[] result = new int[n];
            int count = 0;
            
            for(int i = 0; i < n; i++){
                if(result[i] != 0){
                    continue;
                }
                dfs(result, M, i, ++count);
            }
            return count;
        }
        
        public void dfs(int[] result, int[][] M, int i, int count){
            if(result[i] != 0)
                return;
            result[i] = count;
            
            for(int j = 0; j < M.length; j++){
                if(i != j && M[i][j] == 1){
                    dfs(result, M, j, count);
                }
            }
        }
    }
    

Log in to reply
 

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