public class Solution {
public void dfs(int[][] M, int[] visited, int i) {
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && visited[j] == 0) {
visited[j] = 1;
dfs(M, visited, j);
}
}
}
public int findCircleNum(int[][] M) {
int[] visited = new int[M.length];
int count = 0;
for (int i = 0; i < M.length; i++) {
if (visited[i] == 0) {
dfs(M, visited, i);
count++;
}
}
return count;
}
}
Neat DFS java solution


@vinod23 said in Neat DFS java solution:
It is good solution.
BTW, visited use boolean[] better.


Awesome solution!
I changed theint[] visited
toboolean[] visited
, and it helped me understand your solution better. Here are the codes:public class Solution { public int findCircleNum(int[][] M) { //DFS Solution boolean[] visited = new boolean[M.length]; int count = 0; for(int i = 0; i < M.length; i++) if(!visited[i]) { dfs(M, visited, i); count++; } return count; } private void dfs(int[][] M, boolean[] visited, int i) { for(int j = 0; j < M.length; j++) if(M[i][j] == 1 && !visited[j]) { visited[j] = true; dfs(M, visited, j); } } }

@WeiWeiJump said in Neat DFS java solution:
Is DFS method's time complexity O(n^2) ?
BTW, n is the number of people


You can try to set j in dfs to a special start in order to decrease the number of loops
public int findCircleNum(int[][] M) { int len = M.length; boolean[] set = new boolean[len]; int count = 0; for(int i=0;i<len;i++){ if(!set[i]){ count++; dp(M,i,i,set); } } return count; } public void dp(int[][] M,int loopstart,int start,boolean[] set){ for(int j=loopstart;j<M.length;j++){ if(M[start][j]==1&&!set[j]){ set[j] = true; dp(M,loopstart,j,set); } } }
And this code is faster than 99% Java solution :P

Similar Approach.
public int findCircleNum(int[][] M) { int count = 0; if (M.length == 0) return count; boolean [] seen = new boolean [M.length]; for (int row = 0; row < M.length; row ++) if (!seen [row]) { count ++; helper (seen, M, row); } return count; } private void helper(boolean [] seen, int[][] M, int row) { if (seen [row]) return; seen [row] = true; for (int col = 0; col < M [row].length; col ++) if (M [row][col] == 1) helper (seen, M, col); }