SHARE
TWEET

Untitled

a guest Oct 21st, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // DFS solution: visited array
  2. // Time: O(n^2), 1ms
  3. // Space: O(n), 44.6mb
  4. class Solution {
  5.     public int findCircleNum(int[][] M) {
  6.         int ans = 0;
  7.         int visited[] = new int[M.length];
  8.         for(int i = 0; i < M.length; i++) {
  9.             if(M[i][i] == 1 && visited[i] == 0) {
  10.                 ans++;
  11.                 deleteCircle(M, i, visited);
  12.             }
  13.         }
  14.         return ans;
  15.     }
  16.    
  17.     // Helper method
  18.     private void deleteCircle(int[][] M, int i, int[] visited) {
  19.         // Base case: already delete that user
  20.         if(visited[i] == 1) return;
  21.         visited[i] = 1;
  22.         // For all the friends that the user has
  23.         for(int j = 0; j < M[0].length; j++) {
  24.             if(M[i][j] == 1) deleteCircle(M, j, visited);
  25.         }
  26.     }
  27. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top