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 some var names and added some comments to help understand your logic better. Here is the code:public class Solution { public int findCircleNum(int[][] M) { boolean[] visited = new boolean[M.length]; //visited[i] means if ith person is visited in this algorithm 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 person) { for(int other = 0; other < M.length; other++) { if(M[person][other] == 1 && !visited[other]) { //We found an unvisited person in the current friend cycle visited[other] = true; dfs(M, visited, other); //Start DFS on this new found person } } } }

@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); }

thanks for the clean code and wellnamed variable in the dfs helper function
@dilyar said in Neat DFS java solution:
public class Solution {
public int findCircleNum(int[][] M) {
boolean[] visited = new boolean[M.length]; //visited[i] means if ith person is visited in this algorithm
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 person) {
for(int other = 0; other < M.length; other++) {
if(M[person][other] == 1 && !visited[other]) {
//We found an unvisited person in the current friend cycle
visited[other] = true;
dfs(M, visited, other); //Start DFS on this new found person
}
}
}
}

I pretty much have the same code, but when i try to run it, for the last couple of test cases it says time limit exceeded. Can you help me out by explaining where i am going wrong?
public int solution(int[][] M) { int count = 0; List<Integer> visited = new ArrayList<>(); List<Integer> overall; for(int i=0;i<M.length;i++) { if(!visited.contains(i)) { visited.add(i); overall = recurse(i,visited,M); overall.remove(visited); visited.addAll(overall); count++; } } return count; } public List<Integer> recurse(int visit, List<Integer> visited, int[][] m) { for (int j = 0; j < m.length; j++) { if (m[visit][j] == 1 && !visited.contains(j)) { visited.add(j); recurse(j,visited,m); } } return visited; }