Neat DFS java solution


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

  • 1
    Y

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


  • 0
    B

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


  • 9

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

  • 0
    W

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


  • 0
    W

    @WeiWeiJump said in Neat DFS java solution:

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

    BTW, n is the number of people


  • 0

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


  • 2
    L

    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


  • 1
    A

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

  • 0
    Q
    This post is deleted!

  • 0
    W

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


  • 0
    R

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

Log in to reply
 

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