文字教学

这是一道拓扑排序+动态规划问题，核心是在有向无环图（DAG）上按拓扑序求每个节点的最长路径。

1. 图的存储：用链式前向星存图，避免STL，效率更高。
2. 拓扑排序：因为所有边都是从西往东，图是DAG。按拓扑序处理节点，保证处理一个节点时，它的所有前驱都已处理完。
3. 动态规划：设 dp[i] 表示以 i 为终点的最长路径长度，初始值为1（每个城市自己）。对于边 u→v，更新 dp[v] = max(dp[v], dp[u] + 1)。

代码

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

const int N = 100005;
const int M = 200005;

int hd[N], ed[M], nt[M], cnt;
int in[N], dp[N], q[N], fr, rr;

void add(int u, int v) {
    ed[++cnt] = v;
    nt[cnt] = hd[u];
    hd[u] = cnt;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        in[y]++;
    }
    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
        if (in[i] == 0) {
            q[rr++] = i;
        }
    }
    while (fr < rr) {
        int u = q[fr++];
        for (int i = hd[u]; i; i = nt[i]) {
            int v = ed[i];
            if (dp[v] < dp[u] + 1) {
                dp[v] = dp[u] + 1;
            }
            in[v]--;
            if (in[v] == 0) {
                q[rr++] = v;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d\n", dp[i]);
    }
    return 0;
}