Java Undirected Graph Connected Components


  • 6
    J

    My solution is based on the concept of the connected components in graph, but basically it is a DFS variant.

    It uses O(M N) extra space and has O(M N) time complexity.

     public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) {
            return 0;
        }
    
        final int N = grid.length;
        final int M = grid[0].length;
        final boolean visited[][] = new boolean[N][M];
        int count = 0;
    
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
    
                if(grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j, visited);
                    count++;
                }
            }
        }
        return count;
    } 
    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return;
        } else if(visited[i][j] || grid[i][j] != '1') {
            return;
        }
    
        visited[i][j] = true;
        dfs(grid, i - 1, j, visited);
        dfs(grid, i + 1, j, visited);
        dfs(grid, i, j - 1, visited);
        dfs(grid, i, j + 1, visited);
    }

  • 0
    S

    You dont need to create another visited array. you can use the existing grid and change value to 1. It is like thinking drowning the island.


Log in to reply
 

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