求DAG有向无环图直径 dp

动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
vector<int> g[N], id;
int dp[N];
int main() {
    int n, m;
    sc(n), sc(m);
    for (int i = 0, a, b; i < m; ++i) {
        sc(a), sc(b);
        g[a].emplace_back(b), g[b].emplace_back(a);
    }
    for (int i = 0; i < n; i++) id.emplace_back(i);
    sort(id.begin(), id.end(),
         [&](int a, int b) { return g[a].size() < g[b].size(); });
    // 按度从小到大排序
    int ans = 0;
    for (int i : id) {
        dp[i] = 1;
        for (int j : g[i])
            if (g[j].size() < g[i].size())  // 可以继承
                dp[i] = max(dp[i], dp[j] + 1); // 无权
        ans = max(ans, dp[i]);
    }
    pr(ans);
    return 0;
}