Can anybody figure out why my code is wrong


  • 0
    D
    I would like to use the DFS to connect the graphs and count how many graphs this matrix has, but it indicates stack overflow 
    public class Solution {
    
    public int findCircleNum(int[][] M) {
        if(M == null || M.length == 0){
            return 0;
        }
        boolean[][] visit = new boolean[M.length][M[0].length];
        int count = 0;
        for(int i = 0; i < M.length; i++){
            for(int j = 0; j < M[0].length; j++){
                if(M[i][j] == 1 && visit[i][j] == false){
                    help(i, j, visit, M);
                    count++;
                }
            }
        }
        return count;
    }
    void help(int i, int j, boolean[][] visit, int[][] M){
        if(i < 0 || j < 0 || i >= visit.length || j >= visit.length || M[i][j] == 0){
            return;
        }
            visit[i][j] = true;
            help(i - 1, j, visit, M);
            help(i + 1, j, visit, M);
            help(i, j - 1, visit, M);
            help(i, j + 1, visit, M);
            return;
    }
    

    }


  • 0
    Z

    I would only use 1d array as my visited to record each node instead of 2d array, since this is undirect graph(symmetric matrix), which means edges are duplicate, you may run into some infinite loop problem in this setting.


  • 0
    Z

    Your code has more serious problem...you misunderstood the neighbor relation in this problem. It's not the adjacent cell in matrix, this 2d matrix is a adjacency matrix.


Log in to reply
 

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