拓扑排序扩展

---

⭐ 重要技巧

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

⚠️ 注意

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

最大食物链计数

题目链接

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

思路分析

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

代码实现

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 ]

代码实现

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/

思路分析

代码实现

参加会议的最多员工数

题目链接

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

思路分析

代码实现