DFS,WHY my code ,when the graph is bigger,it would StackoverFlow? help,how to shrink the DFS


  • 1

    public class Solution {

    public int findCircleNum(int[][] M) {
         l = M.length;
        int count=0;
        vis=new int[l][l];
        for(int i=0;i<l;i++){
            for(int j=i;j<l;j++){
                if(0==vis[i][j]&&M[i][j]==1){
                    // M[I][J] <-color.grey
                    vis[i][j]=1;
                    count++;
                    DFS(M,i,j);
                }
            }
        }
        return count;
        
    }
    
    int l;
    int[][] dir = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    int[][] vis ;
    void DFS(int[][] m,int x ,int y){
        
        for(int k=0;k<4;k++){
            int tx=x+dir[k][0];
            int ty=y+dir[k][1];
            if(tx>=0&&tx<l&&ty>=0&&ty<l&&m[tx][ty]==1&&0==vis[tx][ty]){
                
                //m[tx][ty]<-color.grey
                vis[tx][ty]=1;
                DFS(m,tx,ty);
            }
        }
        
    }
    

    }


  • 0
    Y
    This post is deleted!

  • 0
    S

    I have similar solution and same problem. Here is my code:

        class Solution {
    int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public int findCircleNum(int[][] M) {
        if(M == null)
            return 0;
        int m = M.length;
        int n = M[0].length;
        boolean[][] visited = new boolean[m][n];
        int count = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(M[i][j] == 1 && !visited[i][j]){
                    count++;
                    dfs(M, visited, i, j);
                }
            }
        }
        return count;
    }
    
    public void dfs(int[][] M, boolean[][] visited, int i, int j){
        int m = M.length;
        int n = M[0].length;
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j] || M[i][j] == 0)
            return;
        visited[i][j] = true;
        for(int[] dir : dirs){
            dfs(M, visited, i+dir[0], j+dir[1]);
        }
    }
    

    }

    Please, let me know if you find the reason/solution?


Log in to reply
 

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