知识文档站

Appearance

拓扑排序扩展

⭐ 重要技巧 ​

利用拓扑排序的过程，上游节点逐渐推送消息给下游节点的技巧 ​

⚠️ 注意

这个技巧已经是树型dp的内容了，不过即便不会动态规划，本节课也能听懂动态规划专题（包括树型dp）会在后续【必备】课程里讲述 ​

最大食物链计数 ​

题目链接 ​

https://www.luogu.com.cn/problem/P4017 ​

思路分析 ​

以每个节点看作结尾，记录有多少条路径可以到达该节点，将节点的信息推送给与之相连的下一个节点，依次累加统计，得到最终总的食物链条数，采用链式前向星建图 ​

代码实现 ​

java
import java.io.*;
import java.util.Arrays;

public class Main {

    public static int MAXN = 5001;

    public static int MAXM = 500001;

    public static int MOD = 80112002;

    // 链式前向星建图
    public static int[] head = new int[MAXN];

    public static int[] next = new int[MAXM];

    public static int[] to = new int[MAXM];

    public static int cnt;

    // 拓扑排序需要的队列
    public static int[] queue = new int[MAXN];

    // 拓扑排序需要的入度表
    public static int[] indegree = new int[MAXN];

    // 拓扑排序需要的推送信息
    public static int[] lines = new int[MAXN];

    public static int n, m;

    public static void build(int n) {
        cnt = 1;
        Arrays.fill(indegree, 0, n + 1, 0);
        Arrays.fill(lines, 0, n + 1, 0);
        Arrays.fill(head, 0, n + 1, 0);
    }

    // 采用头插，u -> v
    public static void addEdge(int u, int v) {
        // 新的 edge 的 next 伟原来的 head
        next[cnt] = head[u];
        to[cnt] = v;
        // 更新新的 head
        head[u] = cnt++;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            build(n);
            for (int i = 0; i < m; i++) {
                in.nextToken();
                int u = (int) in.nval;
                in.nextToken();
                int v = (int) in.nval;
                // u -> v
                addEdge(u, v);
                indegree[v]++;
            }
            out.println(ways());
        }
        out.flush();
        out.close();
        br.close();
    }

    public static int ways() {
        int l = 0;
        int r = 0;
        // 初始化
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                queue[r++] = i;
                lines[i] = 1;
            }
        }
        int ans = 0;

        // 拓扑排序
        while (l < r) {
            int u = queue[l++];
            // 头边的边号为 0，表示当前节点不再有后续的邻居了
            if (head[u] == 0) {
                // 同于原理
                ans = (ans + lines[u]) % MOD;
            } else {
                for (int ei = head[u]; ei > 0; ei = next[ei]) {
                    // u -> v
                    int v = to[ei];
                    lines[v] = (lines[v] + lines[u]) % MOD;
                    if (--indegree[v] == 0) {
                        queue[r++] = v;
                    }
                }
            }
        }
        return ans;
    }
}

喧闹和富有 ​

题目链接 ​

https://leetcode.cn/problems/loud-and-rich/ ​

思路分析 ​

若 a 比 b 有钱则认为有一条 a 指向 b 的边，题目要求返回 ans 数组，i 位置往 i + 1 位置推送信息，如果发现 i 位置的安静值更小，则更新 i + 1 位置的值 ans [ i + 1 ] 为 ans [ i ] ​

代码实现 ​

java
class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;

        // 邻接表建图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 构建邻接表
        int[] indegree = new int[n];
        for (int[] r : richer) {
            graph.get(r[0]).add(r[1]);
            indegree[r[1]]++;
        }

        int[] queue = new int[n];
        int l = 0;
        int r = 0;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue[r++] = i;
            }
        }

        int[] ans = new int[n];
        // 初始化
        for (int i = 0; i < n; i++) {
            ans[i] = i;
        }

        // 拓扑排序
        while (l < r) {
            int cur = queue[l++];
            for (int next : graph.get(cur)) {
                if (quiet[ans[next]] > quiet[ans[cur]]) {
                    ans[next] = ans[cur];
                }
                if (--indegree[next] == 0) {
                    queue[r++] = next;
                }
            }
        }
        return ans;
    }
}

并行课程 ​

题目链接 ​

https://leetcode.cn/problems/parallel-courses-iii/ ​

思路分析 ​

本题坑点：完成第 i 门课程花费的时间记录在 time [ i - 1 ] 中 ​

首先更新 cost [ i ]，即完成之前任务需要的时间加上完成第 i 门课程的时间，完成之前任务需要的时间和累加更新后的时间取最大值，推消息，cost [ next ] 更新为 cost [ cur ] 和 cost [ next ] 取最大值 ​

举例：完成 a 课程需要 3，完成 b 课程需要 4，且都是 c 的前置课程，则对于 c 而言，时间取值应该取最大，即至少等到 b 完成了才可以开始完成 c，且过程中 a 已经完成 ​

代码实现 ​

java
class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] indegree = new int[n + 1];
        for (int[] edge : relations) {
            graph.get(edge[0]).add(edge[1]);
            indegree[edge[1]]++;
        }
        int[] queue = new int[n + 1];
        int l = 0;
        int r = 0;
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                queue[r++] = i;
            }
        }
        int[] cost = new int[n + 1];
        int ans = 0;
        while (l < r) {
            int cur = queue[l++];
            // 注意：完成 i 的时间记录在 time[i - 1] 中
            cost[cur] += time[cur - 1];
            ans = Math.max(ans, cost[cur]);
            for (int next : graph.get(cur)) {
                cost[next] = Math.max(cost[next], cost[cur]);
                if (--indegree[next] == 0) {
                    queue[r++] = next;
                }
            }
        }
        return ans;
    }
}

参加会议的最多员工数 ​

题目链接 ​

https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/ ​

思路分析 ​

情况一：定义环中人数为 2 的为小环，分别找到环中延申的最长链，再加上中心点的个数 ​

情况二：定义环中人数 > 2 的为大环，大环中无法再融入其他人，即取环中的个数 ​

在环上的点的入度都不会为 0，利用这一特点统计环上节点个数，通过推消息模型记录链的长度，情况一和情况二取最大值即为答案 ​

代码实现 ​

java
class Solution {
    public int maximumInvitations(int[] favorite) {
        // favorite[a] = b 表示 a 喜欢 b
        int n = favorite.length;
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            indegree[favorite[i]]++;
        }
        int[] queue = new int[n];
        int l = 0;
        int r = 0;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue[r++] = i;
            }
        }

        // deep[i] 表示不包括 i 在内，i 之前的最长链的长度
        int[] deep = new int[n];
        while (l < r) {
            int cur = queue[l++];
            int next = favorite[cur];
            deep[next] = Math.max(deep[next], deep[cur] + 1);
            if (--indegree[next] == 0) {
                queue[r++] = next;
            }
        }

        // 情况一：环中节点数为 2，算最长链的个数加上中心点的个数
        int sumOfSmallRings = 0;
        // 情况二：环中节点数 > 2，取环中节点个数
        int bigRings = 0;

        // 遍历环上节点
        for (int i = 0; i < n; i++) {
            // 在环上的点的入度都不会为 0，利用这一特点统计环上节点个数
            if (indegree[i] > 0) {
                int ringSize = 1;
                indegree[i] = 0;
                for (int j = favorite[i]; j != i; j = favorite[j]) {
                    ringSize++;
                    // 标记为 0 的目的是不希望再次遍历在环中的节点，便于找到不同的环
                    indegree[j] = 0;
                }
                // 情况一：小环
                if (ringSize == 2) {
                    sumOfSmallRings += 2 + deep[i] + deep[favorite[i]];
                } else {
                    // 情况二：大环
                    bigRings = Math.max(bigRings, ringSize);
                }
            }

        }
        // 情况一和情况二取最大值即为答案
        return Math.max(sumOfSmallRings, bigRings);
    }
}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1