LeetCode刷题笔记之图论

1. 797【所有可能的路径】

• 题目： 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）。graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
• 代码：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        //深度优先遍历，本质上与回溯算法一样
        //先使用for循环进行遍历每个节点的下一个可到达节点
        //然后在for循环里进行递归遍历每条路径
        //终止条件是到达最后一个节点
        path.add(0);
        dfs(graph,0);
        return ans;
    }
    public void dfs(int[][] graph,int index){
        if(index == graph.length-1){
            ans.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<graph[index].length;i++){
            path.add(graph[index][i]);
            dfs(graph,graph[index][i]);
            path.removeLast();
        }
    }
}

2. 200【岛屿数量】

• 题目： 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
• 代码：

class Solution {
    public int numIslands(char[][] grid) {
        //DFS，设置一个数组记录是否被访问过
        //遍历到一个陆地就进行dfs，land数量加1
        int num = 0;
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] isVisited = new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!isVisited[i][j] && grid[i][j]=='1'){
                    num++;
                    dfs(grid,isVisited,i,j);
                }
            }
        }
        return num;
    }
    public void dfs(char[][] grid,boolean[][] isVisited,int x,int y){
        if(x<0 || x>=grid.length || y<0 || y>=grid[0].length){
            return;
        }
        if(isVisited[x][y] || grid[x][y]=='0'){
            return;
        }
        isVisited[x][y] = true;
        int[][] loc = new int[][]{
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
        };
        for(int i=0;i<4;i++){
            int xTmp = x+loc[i][0];
            int yTmp = y+loc[i][1];
            dfs(grid,isVisited,xTmp,yTmp);
        }
    }
}

3. 695【岛屿的最大面积】

• 题目： 给你一个大小为 m x n 的二进制矩阵 grid 。
  岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
• 代码：

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        //先用dfs找到岛屿，计算每个岛屿的面积
        //记录最大值
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] isVisited = new boolean[m][n];
        int max = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!isVisited[i][j] && grid[i][j]==1){
                    int tmp = dfs(grid,isVisited,i,j);
                    max = Math.max(tmp,max);
                }
            }
        }
        return max;
    }
    public int dfs(int[][] grid,boolean[][] isVisited,int x,int y){
        if(isVisited[x][y] || grid[x][y]==0){
            return 0;
        }
        isVisited[x][y] = true;
        int[][] loc = new int[][]{
            {0,1},
            {0,-1},
            {1,0},
            {-1,0}
        };
        int area = 1;
        for(int i=0;i<4;i++){
            int tmpX = x + loc[i][0];
            int tmpY = y + loc[i][1];
            if(tmpX<0 || tmpX>=grid.length || tmpY<0 || tmpY>=grid[0].length){
                continue;
            }
            area += dfs(grid,isVisited,tmpX,tmpY);
        }
        
        return area;
    }
}

4. 1020【飞地的数量】

• 题目： 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
• 代码：

class Solution {
    int num = 0;
    int[][] loc = new int[][]{
        {0,1},
        {0,-1},
        {1,0},
        {-1,0}
    };
    public int numEnclaves(int[][] grid) {
        //首先使用dfs标记所有边界位置的陆地，
        //然后再遍历内部陆地，同时记录个数
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] isVisited = new boolean[m][n];
        for(int i=0;i<m;i++){
            if(!isVisited[i][0] && grid[i][0]==1) dfs(grid,isVisited,i,0);
            if(!isVisited[i][n-1] && grid[i][n-1]==1) dfs(grid,isVisited,i,n-1);
        }
        for(int i=0;i<n;i++){
            if(!isVisited[0][i] && grid[0][i]==1) dfs(grid,isVisited,0,i);
            if(!isVisited[m-1][i] && grid[m-1][i]==1) dfs(grid,isVisited,m-1,i);
        }
        num = 0;
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++){
                if(!isVisited[i][j] && grid[i][j]==1){
                    dfs(grid,isVisited,i,j);
                }
            }
        }
        return num;
    }
    public void dfs(int[][] grid,boolean[][] isVisited,int x,int y){
        if(grid[x][y]==0 || isVisited[x][y] ){
            return;
        }
        isVisited[x][y] = true;
        num++;
        
        for(int i=0;i<4;i++){
            int tmpX = x + loc[i][0];
            int tmpY = y + loc[i][1];
            if(tmpX<0 || tmpX>=grid.length || tmpY<0 || tmpY>=grid[0].length){
                continue;
            }
            dfs(grid,isVisited,tmpX,tmpY);
        }
    }
}

5. 130【被围绕的区域】

• 题目： 给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

• 代码：

class Solution {
    public void solve(char[][] board) {
        //使用visited数组标注已经访问过的位置
        //先遍历边缘位置，然后对内部未访问过的‘O’替换
        int n = board.length;
        int m = board[0].length;
        boolean[][] visited = new boolean[n][m];
        for(int i=0;i<n;i++){
            if(board[i][0]=='O') dfs(board,i,0,visited);
            if(board[i][m-1]=='O') dfs(board,i,m-1,visited);
        }
        for(int i=0;i<m;i++){
            if(board[0][i]=='O') dfs(board,0,i,visited);
            if(board[n-1][i]=='O') dfs(board,n-1,i,visited);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j] && board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }
    public void dfs(char[][] board,int x,int y,boolean[][] visited){
        if(x<0|| x>=board.length||y<0||y>=board[0].length||visited[x][y]==true){
            return;
        }
        if(board[x][y]=='X') return;
        visited[x][y] = true;
        int[][] loc = new int[][]{
            {1,0},{-1,0},{0,1},{0,-1}
        };
        for(int i=0;i<4;i++){
            int tmpX=x+loc[i][0];
            int tmpY=y+loc[i][1];
            dfs(board,tmpX,tmpY,visited);
        }
    }
}

6. 417【太平洋大西洋水流问题】

• 题目： 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
• 代码：

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        //题目的意思就是找到既能通往太平洋，又能通往大西洋的节点
        //从太平洋一侧遍历找到可以流到太平洋的所有节点
        //从大西洋异常遍历找到可以流到大西洋的所有节点
        //这两次遍历的公共节点即为既能通往太平洋，又能通往大西洋的节点
        int n = heights.length;
        int m = heights[0].length;
        boolean[][][] visited = new boolean[n][m][2];
        for(int i=0;i<n;i++){
            dfs(heights,i,0,visited,0);
            dfs(heights,i,m-1,visited,1);
        }
        for(int i=0;i<m;i++){
            dfs(heights,0,i,visited,0);
            dfs(heights,n-1,i,visited,1);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(visited[i][j][0] && visited[i][j][1]){
                    List<Integer> tmp = new LinkedList<>();
                    tmp.add(i);
                    tmp.add(j);
                    ans.add(tmp);
                }
            }
        }
        return ans;
    }
    public void dfs(int[][] heights,int x,int y,boolean[][][] visited,int dst){
        if(visited[x][y][dst]) return;
        visited[x][y][dst] = true;
        int[][] loc = new int[][]{
            {1,0},{-1,0},{0,1},{0,-1}
        };
        for(int i=0;i<4;i++){
            int tmpX=x+loc[i][0];
            int tmpY=y+loc[i][1];
            if(tmpX<0|| tmpX>=heights.length||tmpY<0||tmpY>=heights[0].length){
                continue;
            }
            if(heights[x][y]<=heights[tmpX][tmpY])
                dfs(heights,tmpX,tmpY,visited,dst);
        }
    }
}

7. 841【钥匙和房间】

• 题目： 有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
  当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
  给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
• 代码：

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //先使用dfs遍历得到所有可以打开的房间，
        //然后判断是否有未打开的房间
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        Arrays.fill(visited,false);
        dfs(rooms,0,visited);
        for(int i=0;i<n;i++){
            if(!visited[i]) return false;
        }
        return true;
    }
    public void dfs(List<List<Integer>> rooms,int x,boolean[] visited){
        if(visited[x]) return;
        visited[x] = true;
        for(int i=0;i<rooms.get(x).size();i++){
            dfs(rooms,rooms.get(x).get(i),visited);
        }
    }
}

8. 463【岛屿的周长】

• 题目： 给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
  网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
  岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

• 代码：

class Solution {
    public int islandPerimeter(int[][] grid) {
        //当陆地旁边是边界或水域时，需要计算周长
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j] && grid[i][j]==1){
                    ans+= dfs(grid,i,j,visited);
                }
            }
        }
        return ans;
    }
    public int dfs(int[][] grid,int x,int y,boolean[][] visited){
        if(x<0||x>=grid.length||y<0||y>=grid[0].length) return 1;
        if(grid[x][y]==0) return 1;
        if(visited[x][y]) return 0;
        visited[x][y] = true;
        int[][] loc = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        int ans = 0;
        for(int i=0;i<4;i++){
            int tmpX=x+loc[i][0];
            int tmpY=y+loc[i][1];
            ans+=dfs(grid,tmpX,tmpY,visited);
        }
        return ans;
    }
}

9. 1971【寻找图中是否存在路径】

• 题目： 有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。
• 代码：

class Solution {
    public int[] fa;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        //可以使用并查集
        //首先初始化每个节点的father节点
        //如果两个节点之间有边，就将两个节点合并到一个集合
        fa = new int[n];
        init();
        for(int i=0;i<edges.length;i++){
            union(edges[i][0],edges[i][1]);
        }
        return find(source)==find(destination);
    }
    public void init(){
        for(int i=0;i<fa.length;i++){
            fa[i] = i;
        }
    }
    public int find(int u){
        if(u==fa[u])
            return u;
        else
            fa[u] = find(fa[u]);
        return fa[u];
    }
    public void union(int u,int v){
        u = find(u);
        v = find(v);
        fa[u] = v;
    }
}

10. 684【冗余连接】

• 题目： 树可以看成是一个连通且无环的无向图。
  给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
  请找出一条可以删去的边，删除后可使得剩余部分是一个有着n个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
• 代码：

class Solution {
    public int[] fa;
    public int[] findRedundantConnection(int[][] edges) {
        //利用并查集，如果某一条边的两个节点处于相同的集合，
        //那么这条边一定会造成环的出现
        //只需判断第一个出现环的边即可找出结果
        fa = new int[edges.length+1];
        init();
        for(int i=0;i<edges.length;i++){
            if(find(edges[i][0]) == find(edges[i][1]))
                return edges[i];
            else union(edges[i][0],edges[i][1]);
        }
        return new int[2];
    }
    public void init(){
        for(int i=1;i<fa.length;i++){
            fa[i] = i;
        }
    }
    public int find(int u){
        if(u==fa[u]) return u;
        else fa[u] = find(fa[u]);
        return fa[u];
    }
    public void union(int u,int v){
        u = find(u);
        v = find(v);
        fa[u] = v;
    }

}