2023 2023 Leetcode Cup Graph Theory List

2022年(上)

2368. 受限条件下可到达节点的数目 Rank:1477

方法一：DFS

Map建图+dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        this.n = n;
        this.edges = edges;
        this.restricted = restricted;
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            graph.putIfAbsent(from, new ArrayList<>());
            graph.putIfAbsent(to, new ArrayList<>());
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
        for (int x : restricted)
            banList.add(x);
        dfs(0, -1);
        return res;
    }

    public void dfs(int node, int parent) {
        ++res;
        List<Integer> nexts = graph.get(node);
        for (int next : nexts) {
            if (next != parent && !banList.contains(next)) {
                dfs(next, node);
            }
        }
    }

    int n, res = 0;
    int[][] edges;
    int[] restricted;
    Map<Integer, List<Integer>> graph = new HashMap<>();
    Set<Integer> banList = new HashSet<>();
}

2385. 感染二叉树需要的总时间 Rank:1711

方法一：DFS + BFS

  • 每遍历一层，秒数加一
  • res初始化为-1，因为如果只有一个节点，答案是0秒，即不需要扩散
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int amountOfTime(TreeNode root, int start) {
        visited.add(start);
        buildGraph(root);
        // for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
        //     System.out.print(entry.getKey() + ": ");
        //     for (int x : entry.getValue()) {
        //         System.out.print(x + " ");
        //     }
        //     System.out.println();
        // }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ++res;
            for (int i = 0; i < size; ++i) {
                int node = queue.poll();
                visited.add(node);
                List<Integer> list = graph.get(node);
                for (int next : list) {
                    if (node != next && !visited.contains(next)) {
                        queue.offer(next);
                    }
                }
            }
        }
        return res;
    }


    public void buildGraph(TreeNode root) {
        if (root == null)
            return;
        graph.putIfAbsent(root.val, new ArrayList<>());
        if (root.left != null) {
            graph.putIfAbsent(root.left.val, new ArrayList<>());
            graph.get(root.val).add(root.left.val);
            graph.get(root.left.val).add(root.val);
            buildGraph(root.left);
        }
        if (root.right != null) {
            graph.putIfAbsent(root.right.val, new ArrayList<>());
            graph.get(root.val).add(root.right.val);
            graph.get(root.right.val).add(root.val);
            buildGraph(root.right);
        }
    }

    Map<Integer, List<Integer>> graph = new HashMap<>();
    int res = -1;
    Set<Integer> visited = new HashSet<>();
    
}

2359. 找到离给定两个节点最近的节点 Rank:1715

方法一：内向基环树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        n = edges.length;
        this.edges = edges;
        int minDist = inf;
        int[] dist1 = calcDistance(node1), dist2 = calcDistance(node2);
        for (int i = 0; i < n; ++i) {
            int d = Math.max(dist1[i], dist2[i]);
            if (d < minDist) {
                res = i;
                minDist = d;
            }
        }
        return res;
     }

     public int[] calcDistance(int x) {
         int[] dist = new int[n];
         Arrays.fill(dist, inf);
         int d = 0;
         while (x != -1 && dist[x] == inf) {
             dist[x] = d++;
             x = edges[x];
         }
         return dist;
     }


    int inf = Integer.MAX_VALUE, n, res = -1;
    int[] edges;
}

2360. 图中的最长环 Rank:1897

方法一：时间戳

也是内向基环树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestCycle(int[] edges) {
        int res = -1, n = edges.length, clock = 1;
        int[] time = new int[n];
        for (int i = 0; i < n; ++i) {
            if (time[i] > 0)
                continue;
            int startTime = clock, x = i;
            while (x != -1) {
                if (time[x] > 0) {
                    if (time[x] >= startTime)
                        res = Math.max(res, clock - time[x]);
                    break;
                }
                time[x] = clock++;
                x = edges[x];
            }
        }
        return res;
    }
}

2467. 树上最大得分和路径 Rank:2053

方法一：时间戳 + 两次dfs

  • 先dfs一次bob的路径，只有找到0的最短路径的节点用时间戳记录
  • 根据规则再对alice路径dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        n = edges.length + 1;
        graph = new List[n];
        this.amount = amount;
        Arrays.setAll(graph, o -> new ArrayList<>());
        time = new int[n];
        Arrays.fill(time, n);
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            graph[from].add(to);
            graph[to].add(from);
        }
        graph[0].add(-1);
        getDistFromRoot(bob, -1, 0);
        dfs(0, -1, 0, 0);
        return res;
    }

    private void dfs(int alice, int parent, int aliceTime, int score) {
        if (aliceTime == time[alice])
            score += amount[alice] / 2;
        if (aliceTime < time[alice])
            score += amount[alice];
        if (graph[alice].size() == 1) {
            res = Math.max(res, score);
            return;
        }
        for (int next : graph[alice])
            if (next != parent)
                dfs(next, alice, aliceTime + 1, score);
    }


    private boolean getDistFromRoot(int cur, int parent, int t) {
        if (cur == 0) {
            time[cur] = t;
            return true;
        }
        for (int next : graph[cur]) {
            if (next != parent && getDistFromRoot(next, cur, t + 1)) {
                time[cur] = t;
                return true;
            }
        }
        return false;

    }

    List<Integer>[] graph;
    int[] time;
    int n;
    int[] amount;
    int res = Integer.MIN_VALUE;
}

2022年(下)

2641. 二叉树的堂兄弟节点 II Rank:1677

方法一：双BFS(双链表实现)

类似换根DP

  1. 首先算出下一层的节点值总和
  2. 再遍历一次当前层，给孩子节点赋值(如果用queue来遍历，无法重复遍历这一次，还需要用数组记录每一层的和)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        List<TreeNode> q = new LinkedList<>();
        q.add(root);
        root.val = 0;
        while (!q.isEmpty()) {
            List<TreeNode> temp = q;
            q = new ArrayList<>();
            int nextLevelSum = 0;
            for (TreeNode node : temp) {
                if (node.left != null) {
                    q.add(node.left);
                    nextLevelSum += node.left.val;
                }
                if (node.right != null) {
                    q.add(node.right);
                    nextLevelSum += node.right.val;
                }
            }
            for (TreeNode node : temp) {
                int childSum = (node.left != null ? node.left.val : 0) + (node.right != null ? node.right.val : 0);
                if (node.left != null)
                    node.left.val = nextLevelSum - childSum;
                if (node.right != null)
                    node.right.val = nextLevelSum - childSum;
            }
        }
        return root;
    }
}

2684. Maximum Number of Moves in a Grid Rank:1626

方法一：BFS

注意用visited数组剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int[][] dirs = new int[][]{{-1, 1}, {0, 1}, {1, 1}};
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; ++i)
            queue.offer(new int[]{i, 0});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int i = node[0], j = node[1];
            res = Math.max(res, j);
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col) && !visited[row][col] && grid[row][col] > grid[i][j]) {
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                    if (col == n - 1)
                        return n - 1;
                }
            }
        }
        return res;
    }

    int m, n, res = 0;

    public boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    
}

方法二：记忆化搜索

和半年前的提交完全一样！一个字母都不差，属实是肌肉记忆了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int maxMoves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        for (int i = 0; i < m; ++i)
            res = Math.max(res, dfs(i, 0));
        return res;
    }

    public int dfs(int i, int j) {
        if (j == n - 1)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        int ans = 0;
        for (int[] dir : dirs) {
            int len = 0;
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] > grid[i][j])
                len = dfs(row, col) + 1;
            ans = Math.max(ans, len);
        }
        return dp[i][j] = ans;
    }

    int m, n, res = 0;
    int[][] dp, dirs = new int[][]{{-1, 1}, {0, 1}, {1, 1}}, grid;

    public boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    
}

2685. Count the Number of Complete Components

方法一：DFS

  • 遍历每个连通分量，将edge数加上当前节点的邻居数，最后这个连通分量的边会被计算两次
  • 如果是完全连通分量，e = (v - 1) * v / 2
  • 由于这里边计算了两次，如果e = (v - 1) * v，那么是完全连通分量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int countCompleteComponents(int n, int[][] edges) {
        graph = new ArrayList[n];
        Arrays.setAll(graph, e -> new ArrayList<>());
        visited = new boolean[n];
        int cnt = 0;
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            graph[x].add(y);
            graph[y].add(x);            
        }
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                e = 0;
                v = 0;
                dfs(i);
                if (e == v * (v - 1))
                    ++cnt;
            }
        }
        return cnt;
    }

    public void dfs(int i) {
        visited[i] = true;
        List<Integer> nexts = graph[i];
        ++v;
        e += nexts.size();
        for (int next : nexts)
            if (!visited[next])
                 dfs(next);
    }

    List<Integer>[] graph;
    boolean[] visited;
    int e, v;
    
}

2642. Design Graph With Shortest Path Calculator Rank:1811

方法一:Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Graph {

    int[][] graph;
    int n, inf = Integer.MAX_VALUE >> 1;

    public Graph(int n, int[][] edges) {
        this.n = n;
        graph = new int[n][n];
        for (int[] arr : graph)
            Arrays.fill(arr, inf);
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            graph[from][to] = weight;
        }
    }
    
    public void addEdge(int[] edge) {
        int from = edge[0], to = edge[1], weight = edge[2];
        graph[from][to] = weight;
    }
    
    public int shortestPath(int from, int to) {
        boolean[] visited = new boolean[n];
        int[] dist = new int[n];
        Arrays.fill(dist, inf);
        dist[from] = 0;
        for (int i = 0; i < n; ++i) { // 每遍历一次，一个节点被visit，需要遍历n次
            int minIndex = -1, minDist = inf;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && dist[j] < minDist) {
                    minIndex = j;
                    minDist = dist[j];
                }
            }
            if (minIndex == -1) // 非连通
                return -1;
            if (minIndex == to)
                return minDist;
            visited[minIndex] = true;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && dist[j] > minDist + graph[minIndex][j])
                    dist[j] = minDist + graph[minIndex][j];
            }
        }
        return dist[to];
    }
}

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */

方法二：堆优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Graph {

    int[][] g;
    int n, inf = Integer.MAX_VALUE >> 1;

    public Graph(int n, int[][] edges) {
        this.n = n;
        g = new int[n][n];
        for (int[] arr : g)
            Arrays.fill(arr, inf);
        for (int[] e : edges) {
            int from = e[0], to = e[1], cost = e[2];
            g[from][to] = cost;
        }
    }
    
    public void addEdge(int[] e) {
        int from = e[0], to = e[1], cost = e[2];
        g[from][to] = cost;
    }
    
    public int shortestPath(int from, int to) {
        boolean[] visited = new boolean[n];
        int[] dist = new int[n];
        Arrays.fill(dist, inf);
        dist[from] = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        queue.offer(new int[]{from, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int node = arr[0], d = arr[1];
            if (visited[node])
                continue;
            visited[node] = true;
            if (node == to)
                return d;
            for (int i = 0; i < n; ++i) {
                if (!visited[i] && dist[i] > d + g[node][i]) {
                    dist[i] = d + g[node][i];
                    queue.offer(new int[]{i, dist[i]});
                }
            }
        }
        return -1;
    }
}

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */

2608. Shortest Cycle in a Graph Rank:1904

方法一：BFS

问：为什么说发现一个已经入队的点，就说明有环？

答：这说明到同一个点有两条不同的路径，这两条路径组成了一个环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int findShortestCycle(int n, int[][] edges) {
        this.n = n;
        graph = new List[n];
        Arrays.setAll(graph, e -> new ArrayList<>());
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            graph[from].add(to);
            graph[to].add(from);
        }
        int res = inf;
        for (int i = 0; i < n; ++i)
            res = Math.min(res, bfs(i));
        return res == inf ? - 1 : res;
    }

    public int bfs(int i) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[i] = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, -1});
        int ans = inf;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int x = node[0], y = node[1];
            for (int next : graph[x]) {
                if (dist[next] < 0) { // not visited
                    dist[next] = dist[x] + 1;
                    queue.offer(new int[]{next, x});
                }
                else if (next != y) // 访问过，且不是父节点，说明两条简单路径交汇，形成环
                    ans = Math.min(ans, dist[x] + dist[next] + 1);
            }
        }
        return ans;
    }

    List<Integer>[] graph;
    int n, inf = Integer.MAX_VALUE;
}

2577. Minimum Time to Visit a Cell In a Grid Rank:2356

方法一：堆优化dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int minimumTime(int[][] grid) {
        if (grid[0][1] > 1 && grid[1][0] > 1)
            return -1;
        m = grid.length;
        n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] arr : dist)
            Arrays.fill(arr, inf);
        dist[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        pq.offer(new int[]{0, 0, 0});
        while (true) {
            int[] node = pq.poll();
            int i = node[0], j = node[1], d = node[2];
            if (i == m - 1 && j == n - 1)
                return d;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col)) {
                    int nd = Math.max(d + 1, grid[row][col]);
                    nd += (nd - row - col) % 2;
                    if (nd < dist[row][col]) {
                        dist[row][col] = nd;
                        pq.offer(new int[]{row, col, nd});
                    }
                }
            }
        }
    }

    int m, n, inf = Integer.MAX_VALUE;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    
}

方法二：二分 + BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int minimumTime(int[][] grid) {
        if (grid[0][1] > 1 && grid[1][0] > 1)
            return -1;
        m = grid.length;
        n = grid[0].length;
        int l = Math.max(m + n - 2, grid[m - 1][n - 1]), r = (int) 1e5 + m + n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, grid))
                r = mid - 1;
            else 
                l = mid + 1;
        }
        return l + (l + m + n) % 2;
    }

    public boolean check(int limit, int[][] grid) {
        boolean[][] visited = new boolean[m][n];
        visited[m - 1][n - 1] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{m - 1, n - 1, limit - 1});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int i = node[0], j = node[1], t = node[2];
            if (i == 0 && j == 0)
                return true;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col) && !visited[row][col] && t >= grid[row][col]) {
                    queue.offer(new int[]{row, col, t - 1});
                    visited[row][col] = true;
                }
            }
        }
        return false;
    }

    int m, n, inf = Integer.MAX_VALUE;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    
}

2812. 找出最安全路径 Rank:2154

方法一：多源BFS + 二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();
        Queue<int[]> queue = new LinkedList<>();
        dist = new int[n][n];
        for (int[] arr : dist)
            Arrays.fill(arr, -1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid.get(i).get(j) == 1) {
                    queue.offer(new int[]{i, j});
                    dist[i][j] = 0;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int i = node[0], j = node[1];
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col) && dist[row][col] < 0) {
                    dist[row][col] = dist[i][j] + 1;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        int l = 0, r = 3 * n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                l = mid + 1;
            else 
                r = mid - 1;
        }
        return r;
    }

    public boolean check(int limit) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        if (dist[0][0] < limit)
            return false;
        queue.offer(new int[]{0, 0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int i = node[0], j = node[1];
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col) && !visited[row][col] && limit <= dist[row][col]) {
                    queue.offer(new int[]{row, col});
                    visited[row][col] = true;
                }
            }
        }
        return visited[n - 1][n - 1];
    }
    

    int n, inf = Integer.MAX_VALUE >> 1;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, dist;

    public boolean isValid(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < n;
    }
    
}
Algorithms > Graph
#图论 #DFS #BFS #Shortest Path Problem #Topological Sort
2023 2023 Leetcode Cup Graph Theory List
https://leopol1d.github.io/2024/01/14/2023-2023-Leetcode-Cup-Graph-Theory-List/
作者
Leopold
发布于
2024年1月14日
许可协议