第 5.11 章：强连通分量与缩点

5.11.0 从一道题出发：受欢迎的牛

先看一道经典题（HAOI 2006，也是 USACO 常见考点「最受欢迎的奶牛」的模型）：

🐄 题目：受欢迎的牛 有 N 头奶牛（N ≤ 10⁴），每头牛都有一个自己崇拜的牛的列表。崇拜关系是单向的：a 崇拜 b 不代表 b 崇拜 a。 一头牛是「明星牛」，当且仅当其他所有牛都崇拜它（注意：明星牛可以崇拜自己，也可以崇拜别的牛）。 求明星牛的数量。

样例：

N=4, M=4
崇拜关系（有向边）：1→2, 2→1, 1→3, 3→4
答案：1（只有 4 号牛被所有牛崇拜：1→2→1 环里的牛都能到 4，3 也能到 4，而 4 谁也到不了却人人能到它）

先试试你会的方法

思路 1：传递闭包（Floyd）。 「a 能到 b」就用邻接矩阵跑一遍 Floyd-Warshall，然后对每头牛检查「其他所有牛都能到它」。这是经典做法——但复杂度 O(N³)，N = 10⁴ 时是 10¹² 次运算，超时。

思路 2：每个点 BFS 一遍。 O(N·(N+M))，同样是 10⁸ 以上，勉强或超时（M 大时必然超）。

关键观察： 样例中 1 和 2 互相崇拜（1→2、2→1）——1 能到的 2 都能到，2 被崇拜的 1 也被崇拜。环上的牛在「可达性」意义上完全等价！如果我们把「互相可达」的牛捏成一个整体，图的规模会大幅缩小，而且捏完之后不会再有环——这就回到了上一章学的 DAG！

「互相可达的极大子图」就是本章的主角：强连通分量（SCC）。把每个 SCC 缩成一个点（缩点），再在缩出来的 DAG 上分析，是本题也是一大批 Gold 题目的通用套路。

拆解这道题需要回答的问题

学习目标：

• 理解强连通分量的定义与「等价类」视角
• 掌握 DFS 生成树中四种边的分类
• 手写 Tarjan 算法：dfn/low 数组、栈、dfn == low 判定
• 了解 Kosaraju 算法并能对比选择
• 掌握缩点建图，理解「Tarjan 的 SCC 编号是逆拓扑序」
• 用「缩点 + DAG DP」解决受欢迎的牛、最大点权路径等经典题

5.11.1 强连通与强连通分量

强连通： 有向图中若顶点 u 和 v 互相可达（u→v 且 v→u 有路径），则称 u、v 强连通。规定每个点与自己强连通。

强连通分量（Strongly Connected Component, SCC）： 极大的强连通子图——子图内任意两点互相可达，且不能再加入任何顶点保持这一性质。

原 图：                     两个 SCC：
  1 ⇄ 2 → 3 → 4              {1,2}  →  {3}  →  {4}
  （1⇄2 是环）                （缩点后是 DAG）

两个视角：

1. 等价类视角： 「互相可达」是一个等价关系（自反、对称、传递），SCC 就是它划分出的等价类。每个点恰属于一个 SCC。
2. 环视角： 一个环上的所有点属于同一 SCC；反过来，SCC 内任意两点都落在某个环上。

核心性质（缩点定理）： 把每个 SCC 收缩为单个顶点、保留分量之间的边，得到的图一定是 DAG。

证明很简单：若缩点后有环 C₁ → C₂ → … → C₁，则这些分量里的点沿环互相可达，本来就该属于同一个 SCC，与「极大」矛盾。∎

这就是本章的解题模板：有环的图 → 求 SCC → 缩点 → 得到 DAG → 用上一章的拓扑序 DP。

5.11.2 DFS 生成树：四种边

Tarjan 算法的所有技巧都建立在 DFS 生成树上。对有向图从某个起点做 DFS，只记录「首次访问每个顶点」所走的边，就得到一棵生成树（森林）。树上的顶点按首次访问顺序编号（时间戳 dfn）。原图的所有边按指向节点的状态分为四类：

        1
       / \
      2   3 ──────┐（前向边 3→6：指向已访问的
      |            6  自己子树中的后代）
      5 ← 4         /
          （树边 1→2, 2→4, 4→5 …）

四种边：
① 树边（tree edge）：指向未访问的点 —— DFS 走过的边
② 反祖边（back edge）：指向当前 DFS 路径上的祖先 —— 环的信号！
③ 横叉边（cross edge）：指向已访问过、但既非祖先也非后代的点
④ 前向边（forward edge）：指向已访问过的、自己子树中的后代

为什么这四种边是理解 Tarjan 的钥匙？

• 反祖边制造环： 边 v → u 指向祖先 u，则路径 u ⇝ v 加上这条边构成环，u、v 属于同一 SCC。
• 横叉边也可能制造环： 若横叉边 x → y 指向的点 y 还「悬而未决」（能绕回 x 的祖先），环同样形成。这正是 Tarjan 需要维护栈的原因——栈里存的是「还没有确定归属的、仍可能参与环的点」。
• 树边、前向边不制造新环（树边本来就是树；前向边的环早已由其他边形成）。

关键引理： 若 u 是某个 SCC 在 DFS 中第一个被访问的点，则该 SCC 的所有点都在 u 的子树中。（u 称为这个 SCC 的「根」。）

反证：若分量里有点 v 不在 u 的子树中，u 到 v 的路径必须有一条边离开 u 的子树；而离开子树的边只能是反祖边或横叉边，它们指向的点在 v 被访问前就已访问完毕——即该点的时间戳更小、其分量已确定或栈中位置在 u 之上，矛盾。∎

于是「找 SCC」=「找每个分量的根」=「判断哪个点的 dfn 等于它能追溯到的最早时间戳」。这就是 Tarjan 算法。

5.11.3 Tarjan 算法

dfn 与 low

对每个顶点 u 维护两个值：

• dfn[u]：u 被访问的时间戳（第几个被访问），每个点唯一。
• low[u]：u 的子树与「子树中一点通过一条非树边能回到的、仍在栈中的点」的 dfn 最小值。直观说：u 及其后代最多**能回溯到多早。

算法维护一个栈：点被访问时入栈；只有当某个点被确认是 SCC 的根时，才把它和它上方的点一起弹出，构成一个 SCC。

三种情况更新 low

DFS 到达 u，先设 dfn[u] = low[u] = ++timer 并把 u 入栈。然后枚举 u 的每条出边 u → v：

⚠️ 第 2 种情况用 dfn[v] 更新而不是 low[v]（细节见 5.11.7 的错误辨析）。

弹出条件：dfn[u] == low[u]

回溯完所有出边后检查：若 dfn[u] == low[u]，说明 u 的整个子树最多只能回到 u 自己——u 就是它所在 SCC 的根（它是这个分量中最早被访问的点）。此时栈中从 u 到栈顶的所有点恰好构成这个 SCC，全部弹出。

#include <bits/stdc++.h>
using namespace std;

int n, m, timer_cnt = 0, scc_cnt = 0;
vector<vector<int>> adj;
vector<int> dfn, low, scc_id;      // scc_id[u]：u 属于第几个 SCC（1 起）
vector<bool> in_stack;
stack<int> stk;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer_cnt;
    stk.push(u);
    in_stack[u] = true;

    for (int v : adj[u]) {
        if (!dfn[v]) {                       // 情况 1：树边
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {            // 情况 2：反祖边 / 横叉边
            low[u] = min(low[u], dfn[v]);
        }
        // 情况 3：v 已访问且不在栈中 → 无操作
    }

    if (dfn[u] == low[u]) {                  // u 是所在 SCC 的根
        ++scc_cnt;
        while (true) {
            int v = stk.top(); stk.pop();
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            if (v == u) break;               // 弹到 u 为止
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    adj.assign(n + 1, {});
    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc_id.assign(n + 1, 0);
    in_stack.assign(n + 1, false);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;                       // 1 起编号
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)             // 图可能不连通，逐点启动
        if (!dfn[i]) tarjan(i);

    for (int i = 1; i <= n; i++)
        cout << "点 " << i << " 属于 SCC " << scc_id[i] << "\n";
    cout << "共 " << scc_cnt << " 个强连通分量\n";
    return 0;
}

样例验证（受欢迎的牛的图：1→2, 2→1, 1→3, 3→4）：

输入：
4 4
1 2
2 1
1 3
3 4

输出：
点 1 属于 SCC 3
点 2 属于 SCC 3
点 3 属于 SCC 2
点 4 属于 SCC 1
共 3 个强连通分量

手动跟踪：访问 1（dfn=1）→ 访问 2（dfn=2）→ 边 2→1 指向栈中祖先，low[2]=1 → 回溯 low[1]=1。回到 1，边 1→3：访问 3（dfn=3）→ 访问 4（dfn=4）→ 4 无出边，dfn[4]==low[4]=4，4 弹栈，SCC #1 = {4}；回溯 3，low[3]==dfn[3]=3，SCC #2 = {3}；最后 dfn[1]==low[1]=1，SCC #3 = {1,2}。

与上面程序的输出一致。注意 Tarjan 弹栈的顺序（4 最先、{1,2} 最后）——这不是巧合，见 5.11.5。

复杂度： 每个点、每条边只处理常数次，O(N + M)。

5.11.4 Kosaraju 算法：两次 DFS

Tarjan 之外的另一条路，思路惊人地简洁：

1. 第一次 DFS（原图）：任意顺序遍历，每个点回溯时（即完成时）记录到一个序列 order 中（后序序列）。
2. 第二次 DFS（反图）：把所有边反向得 Gᵀ，按 order 从后往前依次取未访问的点作起点 DFS，每次遍历到的点集就是一个 SCC。

为什么对？ 直观理解：强连通分量在 G 和 Gᵀ 中完全相同；而「分量间」的可达关系被反转后，从「最先完成 DFS 的分量」开始在反图上走，只能走进和它互相可达的点——恰好是它自己这个分量。

#include <bits/stdc++.h>
using namespace std;

int n, m, scc_cnt = 0;
vector<vector<int>> g, gr;         // 原图、反图
vector<bool> vis;
vector<int> order, scc_id;

void dfs1(int u) {                 // 原图后序
    vis[u] = true;
    for (int v : g[u])
        if (!vis[v]) dfs1(v);
    order.push_back(u);            // 回溯时记录
}

void dfs2(int u) {                 // 反图上染色
    scc_id[u] = scc_cnt;
    for (int v : gr[u])
        if (!scc_id[v]) dfs2(v);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    g.assign(n + 1, {});
    gr.assign(n + 1, {});
    vis.assign(n + 1, false);
    scc_id.assign(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        gr[v].push_back(u);        // 同时建反图
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs1(i);

    for (int i = n - 1; i >= 0; i--) {   // 后序从后往前
        int u = order[i];
        if (!scc_id[u]) {
            ++scc_cnt;
            dfs2(u);
        }
    }

    for (int i = 1; i <= n; i++)
        cout << "点 " << i << " 属于 SCC " << scc_id[i] << "\n";
    return 0;
}

Tarjan vs. Kosaraju

竞赛中两者都常见。Tarjan 的「SCC 编号是逆拓扑序」这个性质缩点时不需要再跑一遍拓扑排序，是很多选手偏爱它的原因；Kosaraju 思路直白、便于现场推导。选一个练熟，另一个理解即可。

5.11.5 缩点：把图变成 DAG

求出 SCC 后，把每个分量缩成一个点，分量之间的边保留（去掉重边与自环），就得到缩点 DAG。这一步是「有环图」通往「DAG DP」的桥梁。

关键性质：Tarjan 的 SCC 编号是逆拓扑序

观察 5.11.3 的样例：SCC {4} 编号 1，SCC {3} 编号 2，SCC {1,2} 编号 3。而缩点 DAG 的边是 {1,2} → {3} → {4}——编号恰好从「拓扑序最后」往「最先」递增。

原因：Tarjan 的弹栈发生在 DFS 回溯完 u 的所有出边之后——一个分量的所有「下游」分量一定先被弹出、先拿到更小的编号。所以：

• 按 SCC 编号从大到小处理 = 按拓扑序处理（不用再跑 Kahn！）；
• 按 SCC 编号从小到大处理 = 按拓扑序处理逆序。

（Kosaraju 则相反：其编号恰好是拓扑正序。）

建新图代码

// 接在 Tarjan 代码之后（scc_id 已求出，scc_cnt 为分量数）
vector<vector<int>> dag(scc_cnt + 1);
vector<long long> scc_w(scc_cnt + 1, 0);   // 分量权值（如：内部点权之和）

for (int u = 1; u <= n; u++) {
    scc_w[scc_id[u]] += w[u];              // w[]：每个点的点权
    for (int v : adj[u]) {
        int a = scc_id[u], b = scc_id[v];
        if (a != b)                        // 去掉自环；重边通常无需去
            dag[a].push_back(b);
        // 若必须去重边：用 set<pair<int,int>> 或排序 unique
    }
}

💡 重边要不要去？ 求「最长路 / 可达性」时重复边不影响正确性（DP 取 max 会自然忽略）；只有「统计边数」「路径计数」类问题才需要去重。

5.11.6 实战一：受欢迎的牛（缩点 + 出度分析）

回到开篇题。 缩点后分析：一个 SCC 里的牛要么全是明星牛、要么全不是（它们互相可达，被崇拜情况完全相同）。于是问题变成：缩点 DAG 中，有多少个点被其他所有点可达？

DAG 中「被所有点可达」的点至多一个吗？不——但注意如果存在这样的点，它必须从任何点出发都能到达它，那么它不能有任何出边指向「别的大块」（否则那个块回不到它）。事实上：

结论： 被所有牛崇拜的牛存在 ⟺ 缩点 DAG 中出度为 0 的分量恰好一个。此时答案为该分量的大小；若出度为 0 的分量有多个（≥2），它们互相不可达，答案为 0。

证明：若出度为 0 的分量恰一个，记为 C。对任意其他分量 D，从 D 出发沿 DAG 走，终点（无出边的分量）必是 C，故 D 中所有牛都能到 C 中所有牛，C 大小即答案。若有 ≥2 个出度为 0 的分量 C₁、C₂，则 C₁ 到不了 C₂，C₂ 里的牛不是明星，C₁ 的牛也到不了 C₂……所有牛都不是明星，答案 0。∎

#include <bits/stdc++.h>
using namespace std;

int n, m, timer_cnt = 0, scc_cnt = 0;
vector<vector<int>> adj;
vector<int> dfn, low, scc_id, scc_size;
vector<bool> in_stack;
stack<int> stk;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer_cnt;
    stk.push(u);
    in_stack[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        while (true) {
            int v = stk.top(); stk.pop();
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            scc_size[scc_cnt]++;
            if (v == u) break;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    adj.assign(n + 1, {});
    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc_id.assign(n + 1, 0);
    scc_size.assign(n + 1, 0);
    in_stack.assign(n + 1, false);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);

    // 统计每个 SCC 的出度（只统计跨分量的边）
    vector<int> outdeg(scc_cnt + 1, 0);
    for (int u = 1; u <= n; u++)
        for (int v : adj[u])
            if (scc_id[u] != scc_id[v])
                outdeg[scc_id[u]]++;

    int zero_cnt = 0, answer = 0;
    for (int c = 1; c <= scc_cnt; c++)
        if (outdeg[c] == 0) {
            zero_cnt++;
            answer = scc_size[c];
        }

    if (zero_cnt == 1) cout << answer << "\n";
    else               cout << 0 << "\n";
    return 0;
}

样例验证：

输入：            输出：
4 4               1
1 2
2 1
1 3
3 4

缩点后 DAG：{1,2}（大小 2）→ {3} → {4}。出度为 0 的分量只有 {4}，大小 1，输出 1 ✓。与开篇手算一致。再测一个反例：加一条边 4→3（构成 3⇄4 环），则 {3,4} 出度 0、{1,2} 出度 0，两个零出度分量 → 输出 0 ✓（3、4 互相崇拜但 1 崇拜不到 4 之外……实际是 {1,2} 的牛到不了被全部牛崇拜的状态）。复杂度 O(N + M)，10⁴ 规模轻松通过。

5.11.7 ⚠️ 常见错误辨析

详解错误 1（经典面试题级别）： 为什么 SCC 用 dfn[v]？low 的定义是「子树通过非树边能触及的最早 dfn」。当 u 通过反祖/横叉边看到 v 时，这条边只有一条，u 经由它能回到的最早点就是 v 本身（dfn[v]）——不能把 v 的整个子树「打包带走」，因为 v 的其他后代可能是从别的分支进入的，u 不一定能通过它们回去。若用 low[v] 更新，会把不相干的分量错误连通，SCC 变大变少。而无向图的割点/割边没有「横叉边」概念（无向 DFS 树中非树边必是反祖边），用 low[v] 更新反而是正确的——这正是两个 Tarjan 最容易混淆之处。

详解错误 2： 不判 in_stack 的后果：v 已属于某个完成的 SCC（已弹栈），u 显然不能与 v 同分量，但 dfn[v] 仍会被拿来拉低 low[u]，导致 u 的 low 小于真实值，弹栈判定 dfn[u]==low[u] 提前/错误成立，分量分裂或合并。in_stack 就是「这个点还悬而未决、可能与 u 成环」的标记。

5.11.8 实战二：最大点权路径（缩点 + DAG DP）

** cows 版题面（USACO 风格）：**

🐄 题目：观光路线 有 N 个景点（N ≤ 10⁴），景点 i 的观赏值为 w[i]（可正可负，|w[i]| ≤ 10⁵）。景点之间有 M 条单向观光道（M ≤ 10⁵）。 你可以从任意景点出发、在任意景点结束，观光道可以重复走；但每个景点的观赏值只计一次。 求能获得的 maximum 总观赏值（至少要游览一个景点）。

分析： 一般图 + 可重复经过 + 权只算一次——最短路/最长路算法全部失效。但「重复经过」恰恰意味着：同一个环上的所有点要么都经过、要么都不经过（进了一个环就能把环上每个点都逛到）。所以把每个 SCC 缩成一点、点权 = 分量内点权之和，问题变成缩点 DAG 上的「任意起点的最大权路径」——上一章的 DAG DP 直接解决。

转移方程： dp[c] = scc_w[c] + max(0, max over 后继 d 的 dp[d])（0 表示在此分量结束）。由于 dp[c] 依赖后继的 dp 值，要先算后继——而 Tarjan 编号正是逆拓扑序（后继分量编号更小），所以按编号从小到大处理即可，连拓扑排序都省了。

#include <bits/stdc++.h>
using namespace std;

int n, m, timer_cnt = 0, scc_cnt = 0;
vector<vector<int>> adj;
vector<int> dfn, low, scc_id;
vector<bool> in_stack;
stack<int> stk;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer_cnt;
    stk.push(u);
    in_stack[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        while (true) {
            int v = stk.top(); stk.pop();
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            if (v == u) break;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) cin >> w[i];

    adj.assign(n + 1, {});
    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc_id.assign(n + 1, 0);
    in_stack.assign(n + 1, false);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);

    // 缩点建 DAG，累加分量权
    vector<vector<int>> dag(scc_cnt + 1);
    vector<long long> scc_w(scc_cnt + 1, 0);
    for (int u = 1; u <= n; u++) {
        scc_w[scc_id[u]] += w[u];
        for (int v : adj[u])
            if (scc_id[u] != scc_id[v])
                dag[scc_id[u]].push_back(scc_id[v]);
    }

    // Tarjan 编号从小到大 = 逆拓扑序（后继分量编号更小，先算完）
    vector<long long> dp(scc_cnt + 1, 0);
    long long answer = LLONG_MIN;
    for (int c = 1; c <= scc_cnt; c++) {
        long long best_next = 0;             // 0：路径在此分量结束
        for (int d : dag[c])
            best_next = max(best_next, dp[d]);
        dp[c] = scc_w[c] + best_next;
        answer = max(answer, dp[c]);
    }

    cout << answer << "\n";
    return 0;
}

样例验证（手算）：

输入：
5 6
2 3 1 5 4        （w[1..5]）
1 2
2 1
2 3
3 4
4 5
5 3

输出：
15

SCC：{1,2}（权 2+3=5，编号 2）、{3,4,5}（权 1+5+4=10，编号 1）。DAG：{1,2} → {3,4,5}。dp[{3,4,5}] = 10，dp[{1,2}] = 5 + 10 = 15。答案 15 ✓（路线：1→2→3→4→5，环 3⇄4⇝5⇝3 全逛到，值 2+3+1+5+4=15）。

再测单点负权：输入 2 1 / -5 -7 / 1 2，SCC {1}、{2}，dp[2]=-7，dp[1]=max(-5, -5-7)=-5，答案 -5（只游览 1 号）✓。

5.11.9 本章总结

📌 核心要点

🔗 与前后章节的联系

• 第 5.10 章（拓扑排序与 DAG DP）： 本章是它的直接续章——环是拓扑排序唯一处理不了的障碍，缩点彻底扫清它；缩点后的 DP 完全复用上一章技术。
• 第 5.10 章的 2-SAT 一节： 2-SAT 的解法正是「建蕴含图 → 求 SCC → 同分量即矛盾」，本章让你真正看懂那套代码。
• Platinum 预告： 无向图的割点、割边（边双/点双连通分量）是 Tarjan low 思想的又一应用，注意与本章 SCC 版本的 dfn[v] vs low[v] 区别。

🏋️ 练习题

🟢 简单

5.11-E1. 分量计数 给定 N 个顶点、M 条边的有向图，输出强连通分量的个数，以及最大的分量包含多少个顶点。 数据规模： 1 ≤ N ≤ 10⁵，0 ≤ M ≤ 2×10⁵。

🟡 中等

5.11-M1. Network of Schools （POJ 1236，经典）* N 个学校通过单向网络共享软件：学校 i 收到软件后会分发给它的邻接学校。问：(1) 至少向多少学校分发软件，才能让所有学校都拿到？(2) 至少添加多少条边，能使任一学校发出的软件能到达所有学校？ 数据规模： N ≤ 100。

5.11-M2. 最少添加边 给定 N 个顶点、M 条边的有向图，问至少添加多少条有向边，使整张图强连通。 数据规模： 1 ≤ N ≤ 10⁵，1 ≤ M ≤ 2×10⁵。

🔴 困难

5.11-H1. 最大点权路径加强版 （USACO 风格，洛谷 P3387 变体）* 给定 N 个点、M 条边、点权 w[i]（可为负）的有向图，指定起点 S，路径可重复经过点但点权只算一次，求从 S 出发能获得的最大总点权（必须从 S 出发，S 的权一定计入）。 数据规模： 1 ≤ N ≤ 10⁴，1 ≤ M ≤ 10⁵，|w[i]| ≤ 10³。

5.11-H2. 受欢迎的牛加强版 （思考题）* 把「明星牛」改为「被至少 K 头牛（含自己）崇拜的牛」的数量，K 由输入给出。N ≤ 10⁴。缩点后如何在 DAG 上高效统计「每个分量被多少牛可达」？ 数据规模： 1 ≤ K ≤ N ≤ 10⁴，1 ≤ M ≤ 5×10⁴。