图论

图的种类，

度，出度，入度

有多少条边连接这个节点就是几度

连通性

• 连通图

  在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图

• 强连通图

  指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图

• 连通分量

• 强连通分量

• 弱连通图

  将有向图的所有的有向边替换为无向边后，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

图的构造

图的遍历

深搜与广搜

并查集

最小生成树

拓扑排序

最短路算法

岛屿数量

    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        boolean visited[][] = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    int re = dfs(grid, i, j, visited);
                    if (re > 0) {
                        res++;
                    }
                }
            }
        }
        return res;
    }

    public int dfs(char[][] grid, int i, int j, boolean[][] visited) {
        int count = 0;
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0' || visited[i][j]) {
            return count;
        }
        visited[i][j] = true;
        count++;
        count += dfs(grid, i - 1, j, visited);
        count += dfs(grid, i + 1, j, visited);
        count += dfs(grid, i, j - 1, visited);
        count += dfs(grid, i, j + 1, visited);
        return count;
    }

岛屿的最大面积

https://leetcode.cn/problems/ZL6zAn/description/

    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    res = Math.max(res, dfs(grid, i, j));
                }
            }
        }
        return res;
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        return 1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
    }

孤岛总面积

import java.util.Scanner;

/**
 * @author : feixiang.li
 * @since : 2025-07-08 17:47
 */
public class Main {


    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];

        // 孤岛的总面积
        // 首先将边缘的岛屿进行标记
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1 && (i == 0 || i == grid.length - 1 || j == 0 || j == grid[i].length - 1)) {
                    dfs_keep(grid, i, j, visited);
                }
            }
        }


        for (int i = 1; i < grid.length - 1; i++) {
            for (int j = 1; j < grid[i].length - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                     res += dfs(grid, i, j, visited);
                }
            }
        }
        return res;
    }

    private int dfs_keep(int[][] grid, int i, int j, boolean[][] visited) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0 || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        grid[i][j] = 0;
        return 1 + dfs(grid, i - 1, j, visited) + dfs(grid, i + 1, j, visited) + dfs(grid, i, j - 1, visited) + dfs(grid, i, j + 1, visited);
    }

    private int dfs(int[][] grid, int i, int j, boolean[][] visited) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0 || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(grid, i - 1, j, visited) + dfs(grid, i + 1, j, visited) + dfs(grid, i, j - 1, visited) + dfs(grid, i, j + 1, visited);
    }

    public static void main(String[] args) {
        // 开始读取 stdin
        /**
         * 4 5
         * 1 1 0 0 0
         * 1 1 0 0 0
         * 0 0 1 0 0
         * 0 0 0 1 1
         */
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        System.out.println(new Main().maxAreaOfIsland(grid));
    }
}

沉默孤岛

水流问题

package com.lkcoffee.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Date;
import java.util.List;
import java.util.Scanner;

public class Main {


    public void findContinuousSequence(int[][] target) {
        List<List<Integer>> res = new ArrayList<>();

        boolean[][] visited1 = new boolean[target.length][target[0].length];
        boolean[][] visited2 = new boolean[target.length][target[0].length];
        for (int i = 0; i < target.length; i++) {
            for (int j = 0; j < target[i].length; j++) {
                // 遍历左边界和上边界
                if (j == 0 || i == 0) {
                    dfs(target, i, j, visited1, target[i][j]);
                }
                // 遍历右边界和下边界
                if (j == target[i].length - 1 || i == target.length - 1) {
                    dfs(target, i, j, visited2, target[i][j]);
                }
            }
        }
        // 输出结果
        for (int i = 0; i < target.length; i++) {
            for (int j = 0; j < target[i].length; j++) {
                if (visited1[i][j] && visited2[i][j]) {
                    System.out.println(i + " " + j);
                }
            }
        }
    }

    public void dfs(int[][] arr, int i, int j, boolean[][] visited, int target) {
        // 如果当前节点小于上一个节点
        if (i < 0 || i >= arr.length || j < 0 || j >= arr[0].length || arr[i][j] < target || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        /**
         * 现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。
         * 矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，
         * 但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。
         */
        dfs(arr, i - 1, j, visited, arr[i][j]);
        dfs(arr, i + 1, j, visited, arr[i][j]);
        dfs(arr, i, j - 1, visited, arr[i][j]);
        dfs(arr, i, j + 1, visited, arr[i][j]);
    }


    public static void main(String[] args) {
        /**
         * 5 5
         * 1 3 1 2 4
         * 1 2 1 3 2
         * 2 4 7 2 1
         * 4 5 6 1 1
         * 1 4 1 2 1
         */
        Main s = new Main();
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        s.findContinuousSequence(arr);
    }
}

岛屿的周长

    public int islandPerimeter(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    res += getData(i - 1, j, grid) + getData(i + 1, j, grid) + getData(i, j - 1, grid) + getData(i, j + 1, grid);
                }
            }
        }
        return res;
    }

    private int getData(int i, int j, int[][] grid) {
        // 判断上下左右是不是超过边界或者是水
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == 0) {
            return 1;
        }
        return 0;
    }

108 单词接龙p-

class Solution {
  public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int res = 0;
        HashSet<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) {
            return 0;
        }
        Map<String, Integer> map = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            // 广度优先
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                for (int j = 0; j < cur.length(); j++) {
                    char[] chars = cur.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String temp = new String(chars);
                        if (temp.equals(endWord)) {
                            return res + 1;
                        }
                        // 找到所有匹配的字符串,并且没有被遍历过
                        if (set.contains(temp) && !map.containsKey(temp)) {
                            queue.add(temp);
                            map.put(temp, res);
                        }
                    }
                }
            }
        }
        return 0;
    }
}

有向图的完全联通

https://kamacoder.com/problempage.php?pid=1177

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public int findShortestPath(List<Integer>[] graph) {
        int n = graph.length;
//        System.out.println("nn->" + n);
        boolean[] visited = new boolean[n + 1];
        findShortestPath(graph, 1, visited);
        for (int i = 1; i < n; i++) {
            if (!visited[i]) {
                return -1;
            }
        }
        return 1;
    }


    public void findShortestPath(List<Integer>[] graph, int node, boolean[] visited) {
        // 如果已经访问过了
        if (visited[node]) {
            return;
        }
        visited[node] = true;
        for (int neighbor : graph[node]) {
            findShortestPath(graph, neighbor, visited);
        }
    }


    public static void main(String[] args) {

        /**
         * 4 4
         * 1 2
         * 2 1
         * 1 3
         * 2 4
         */
        Main s = new Main();
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        List<Integer>[] graph = new ArrayList[m + 1];
        for (int i = 0; i <= m; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
        }
        System.out.println(s.findShortestPath(graph));
    }
}

并查集

https://blog.csdn.net/knoci/article/details/138542095

const int N = 200010;
 
int p[N]; // p[i] 表示节点 i 的父节点
 
// 初始化并查集
void init(int n) {
    for (int i = 0; i < n; i++) {
        p[i] = i; // 初始化每个节点的父节点为自身
    }
}
 
// 查找节点 u 的根，并进行路径压缩
int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]); // 如果节点 u 的父节点不是自身，则递归查找其父节点，并进行路径压缩
}
 
// 将节点 u 和节点 v 所在的集合合并
void merge(int u, int v) {
    u = find(u); // 寻找节点 u 的根
    v = find(v); // 寻找节点 v 的根
    if (u == v) return; // 如果节点 u 和节点 v 已经在同一个集合中，则不需要连接，直接返回
    p[v] = u; // 将节点 v 的根连接到节点 u 的根上
}
 
// 判断节点 u 和节点 v 是否属于同一个集合
bool isSame(int u, int v) {
    u = find(u); // 寻找节点 u 的根
    v = find(v); // 寻找节点 v 的根
    return u == v; // 如果节点 u 和节点 v 的根相同，则它们属于同一个集合，返回 true，否则返回 false
}

并查集将2个元素合并成同一个集合

判断2个元素是否属于同一个集合

寻找存在的路径

https://kamacoder.com/problempage.php?pid=1179

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static int[] dist;


    public static int find(int a) {
        if (dist[a] == a) {
            return a;
        }
        int temp = find(dist[a]);
        dist[a] = temp;
        return temp;
    }


    public static void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        dist[a] = b;
    }

    boolean isSame(int a, int b) {
        a = find(a);
        b = find(b);
        return a == b;
    }

    public static void main(String[] args) {

        /**
         * 4 4
         * 1 2
         * 2 1
         * 1 3
         * 2 4
         */
        Main s = new Main();
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        dist = new int[m + 1];
        for (int i = 0; i <= m; i++) {
            dist[i] = i;
        }
        for (int i = 0; i < n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            merge(a, b);
        }
        int from = scanner.nextInt();
        int to = scanner.nextInt();
        if (s.isSame(from, to)) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }
    }
}

冗余连接

https://kamacoder.com/problempage.php?pid=1181

https://leetcode.cn/problems/redundant-connection/description/

    static int[] dist;


    public static int find(int a) {
        if (dist[a] == a) {
            return a;
        }
        int temp = find(dist[a]);
        dist[a] = temp;
        return temp;
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        dist = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dist[i] = i;
        }
        for (int i = 0; i < n; i++) {
            int a = find(edges[i][0]);
            int b = find(edges[i][1]);
            if (a != b) {
                dist[a] = b;
            } else {
                return edges[i];
            }
        }
        return null;
    }

冗余连接2

class Solution {
   
      
    static int[] dist;


    public static int find(int a) {
        if (dist[a] == a) {
            return a;
        }
        int temp = find(dist[a]);
        dist[a] = temp;
        return temp;
    }


    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] count = new int[n + 1];
        // 统计入库为
        List<Integer>[] res = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = new ArrayList<>();
        }

        int find = -1;
        for (int i = 0; i < n; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            res[from].add(to);
            count[to]++;
            if (count[to] == 2) {
                find = to;
            }
        }

        // 找不到入库为2的节点，说明已经是一个环了
        if (find == -1) {
            return findRedundantConnection(edges);
        } else {

            // 找到入库为2的2条边
            List<Integer> ans = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (edges[i][1] == find) {
                    ans.add(edges[i][0]);
                }
            }
            int tmp = find;
            res[ans.get(1)].removeIf(item -> item == tmp);
            if (isTree(res)) {
                return new int[]{ans.get(1), find};
            } else {
                return new int[]{ans.get(0), find};
            }
        }
    }


    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        dist = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dist[i] = i;
        }
        for (int i = 0; i < n; i++) {
            int a = find(edges[i][0]);
            int b = find(edges[i][1]);
            if (a != b) {
                dist[a] = b;
            } else {
                return edges[i];
            }
        }
        return null;
    }


    public static boolean isTree(List<Integer>[] res) {
        int n = res.length;
        dist = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dist[i] = i;
        }
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[i].size(); j++) {
                int to = res[i].get(j);
                if (find(i) != find(to)) {
                    merge(i, to);
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    public static void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        dist[a] = b;
    }

}

1584连接所有点点最小值

https://leetcode.cn/problems/min-cost-to-connect-all-points/description/

class Solution {
   public int distance(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            dist[i] = distance(points[i], points[0]);
        }
        dist[0] = 0;
        int cost = 0;
        visited[0] = true;
        for (int i = 1; i < n; i++) {
            int pos = -1;
            int minCost = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minCost) {
                    pos = j;
                    minCost = dist[j];
                }
            }
            cost += minCost;
            visited[pos] = true;
            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    dist[j] = Math.min(dist[j], distance(points[pos], points[j]));
                }
            }
        }
        return cost;
    }
}

778. 水位上升的泳池中游泳

https://leetcode.cn/problems/swim-in-rising-water/description/

class Solution {
   
    int[] p;
    int n;

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    void union(int x, int y) {
        p[find(x)] = p[find(y)];
    }

    boolean query(int x, int y) {
        return p[find(x)] == p[find(y)];
    }

    int getIndex(int x, int y) {
        return x * n + y;
    }

    public int swimInWater(int[][] grid) {
        n = grid.length;
        p = new int[n * n];
        for (int i = 0; i < n * n; i++) p[i] = i;

        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int id1 = getIndex(i, j);
                if (i + 1 < n) {
                    int id2 = getIndex(i + 1, j), w = Math.max(grid[i][j], grid[i + 1][j]);
                    edges.add(new int[]{id1, id2, w});
                }
                if (j + 1 < n) {
                    int id2 = getIndex(i, j + 1), w = Math.max(grid[i][j], grid[i][j + 1]);
                    edges.add(new int[]{id1, id2, w});
                }
            }
        }
        Collections.sort(edges, (o1, o2) -> {
            return o1[2] - o2[2];
        });
        int start = 0;
        int end = getIndex(n - 1, n - 1);
        for (int i = 0; i < edges.size(); i++) {
            int[] edge = edges.get(i);
            int u = edge[0], v = edge[1], w = edge[2];
            union(u, v);
            if (find(start) == find(end)) {
                return w;
            }
        }
        return 0;
    }

}

1631

https://leetcode.cn/problems/path-with-minimum-effort/description/