# Neat DFS java solution

• ``````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;
}
}``````

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

• @vinod23 Nice and clear solution, like it, keep doing awesome work!

• 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
}
}
}
}
``````

• Is DFS method's time complexity O(n^2) ?

• Is DFS method's time complexity O(n^2) ?

BTW, n is the number of people

• @WeiWeiJump I believe so, basically it traverses each element in the input matrix

• 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);
}
``````

• This post is deleted!

• thanks for the clean code and well-named 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))
{
overall = recurse(i,visited,M);
overall.remove(visited);
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))
{
recurse(j,visited,m);
}
}
return visited;
}
``````

• non-recursive code:

``````    public int findCircleNum(int[][] M) {
boolean[] visited = new boolean[M.length];
int count = 0;
for (int i = 0; i < M.length; i++) {
if (dfs(M, visited, i))
count++;
}
return count;
}

private boolean dfs(int[][] M, boolean[] visited, int i) {
if (visited[i]) return false;

Stack<Integer> st = new Stack<>();
st.push(i);
for (; !st.isEmpty();) {
i = st.pop();
visited[i] = true;
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && !visited[j])
st.push(j);
}
}
return true;
}
``````

• @lxydotcom
looks like bfs?

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