求DAG有向无环图直径 dp
Game Map
https://ac.nowcoder.com/acm/contest/13506/C
动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。
#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;
} 算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题
