有向无环图的拓扑排序

int indeg[MAXN];
vector<int> g[MAXN];          // 邻接表存图
vector<int> ans;               // 存放拓扑序

bool kahn(int n) {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);        // ② 入度为 0 的点入队

    while (!q.empty()) {
        int u = q.front(); q.pop();
        ans.push_back(u);                    // ③ 出队即确定位置

        for (int v : g[u]) {
            if (--indeg[v] == 0)          // ④ 删边 + 入度减一
                q.push(v);                   // ⑤ 归零则入队
        }
    }
    return (int)ans.size() == n;        // ⑥ 长度不足 n ⇒ 有环
}

/* ===== 写法一：Kahn 判环（推荐） ===== */
bool hasCycle(int n) {
    queue<int> q;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cnt++;
        for (int v : g[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return cnt < n;               // 输出不足 n 个 ⇒ 有环
}

/* ===== 写法二：DFS 三色标记法 ===== */
int color[MAXN];                 // 0 未访问 / 1 访问中 / 2 已完成
bool cyc = false;

void dfsCheck(int u) {
    color[u] = 1;                          // 进入：标记"访问中"
    for (int v : g[u]) {
        if (color[v] == 1) { cyc = true; return; }   // 遇到祖先 → 有环
        if (color[v] == 0) { dfsCheck(v); if (cyc) return; }
    }
    color[u] = 2;                          // 离开：标记"已完成"
}

void kahnLex(int n) {
    priority_queue<int, vector<int>, greater<int>> pq;   // 小根堆
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) pq.push(i);

    while (!pq.empty()) {
        int u = pq.top(); pq.pop();        // 每次取编号最小的
        cout << u << ' ';
        for (int v : g[u])
            if (--indeg[v] == 0) pq.push(v);
    }
    cout << endl;
}

// ① 先求拓扑序（存进 order[]）
kahn(n);                        // 把结果放在 order 数组里

// ② 初始化
const long long NINF = -1e18;
for (int i = 1; i <= n; i++) dp[i] = NINF;
dp[s] = 0;

// ③ 按拓扑序推进
for (int idx = 0; idx < (int)order.size(); idx++) {
    int u = order[idx];
    if (dp[u] == NINF) continue;             // u 不可达，跳过
    for (auto& ed : g[u]) {                  // ed = (v, w)
        int v = ed.first;
        long long w = ed.second;
        if (dp[u] + w > dp[v]) dp[v] = dp[u] + w;   // 最长路
        // 若是路径计数：dp[v] = (dp[v] + dp[u]) % MOD;
    }
}

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

const int MAXN = 100005;
int indeg[MAXN];
vector<int> g[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        indeg[v]++;                       // 读边时顺便统计入度
    }

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);   // 入度为 0 的点先入队

    vector<int> ans;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ans.push_back(u);
        for (int v : g[u])
            if (--indeg[v] == 0)
                q.push(v);
    }

    if ((int)ans.size() < n) {
        cout << -1 << endl;               // 有环
        return 0;
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

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

const int MAXN = 100005;
const long long NINF = -1e18;

int indeg[MAXN];
long long dp[MAXN];
vector<pair<int, long long>> g[MAXN];   // (终点, 边权)
vector<int> order;

bool kahn(int n) {                  // 顺便判环
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (auto& ed : g[u])
            if (--indeg[ed.first] == 0) q.push(ed.first);
    }
    return (int)order.size() == n;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        indeg[v]++;
    }

    if (!kahn(n)) { cout << "有环" << endl; return 0; }

    for (int i = 1; i <= n; i++) dp[i] = NINF;
    dp[s] = 0;

    for (int u : order) {
        if (dp[u] == NINF) continue;             // u 不可达
        for (auto& ed : g[u]) {
            int v = ed.first;
            long long w = ed.second;
            if (dp[u] + w > dp[v]) dp[v] = dp[u] + w;
        }
    }

    for (int i = 1; i <= n; i++)
        cout << (dp[i] == NINF ? -1 : dp[i]) << " \n"[i == n];
    return 0;
}

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

const int MAXN = 5005, MAXM = 500005;
const long long MOD = 80112002;

int indeg[MAXN], outdeg[MAXN];
long long w[MAXN];                 // w[v]：到达 v 的食物链条数
vector<int> g[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;                     // u 被 v 吃：u → v
        cin >> u >> v;
        g[u].push_back(v);
        indeg[v]++;
        outdeg[u]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) { q.push(i); w[i] = 1; }   // 生产者起始为 1

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            w[v] = (w[v] + w[u]) % MOD;                  // 路径计数
            if (--indeg[v] == 0) q.push(v);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (outdeg[i] == 0) ans = (ans + w[i]) % MOD;    // 只统计最高级消费者

    cout << ans << endl;
    return 0;
}

const int MAXN = 100005;
int indeg[MAXN];
vector<int> g[MAXN];
vector<int> order;

bool kahn(int n) {                 // 返回 true 表示无环
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : g[u])
            if (--indeg[v] == 0) q.push(v);
    }
    return (int)order.size() == n;
}

const long long NINF = -1e18, MOD = 80112002;
long long dp[MAXN], way[MAXN];

// 前提：已用 kahn() 求出 order[]，且图无环
void dagDP(int n, int s) {
    for (int i = 1; i <= n; i++) { dp[i] = NINF; way[i] = 0; }
    dp[s] = 0;
    way[s] = 1;

    for (int u : order) {
        if (dp[u] == NINF && way[u] == 0) continue;   // u 不可达
        for (auto& ed : g[u]) {
            int v = ed.first;
            long long w = ed.second;
            // 最长路：dp[v] = max(dp[v], dp[u] + w);
            // 最短路：dp[v] = min(dp[v], dp[u] + w);
            // 路径计数：way[v] = (way[v] + way[u]) % MOD;
            (void)v; (void)w;
        }
    }
}

// 读边时反向建图
for (int i = 1; i <= m; i++) {
    int x, y; cin >> x >> y;      // 原意：x 必须在 y 之前
    rg[y].push_back(x);              // 反向图：y → x
    indeg[x]++;                      // 注意是 x 的入度 +1（反向图里 x 的入边来自 y）
}

priority_queue<int> pq;               // 默认大根堆
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) pq.push(i);

vector<int> res;
while (!pq.empty()) {
    int u = pq.top(); pq.pop();
    res.push_back(u);
    for (int v : rg[u])
        if (--indeg[v] == 0) pq.push(v);
}
if ((int)res.size() < n) { cout << "Impossible!" << endl; continue; }
for (int i = n - 1; i >= 0; i--)
    cout << res[i] << " \n"[i == 0];   // 倒序输出