求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;
}
算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

07-21 18:43
门头沟学院 Java
是暑期都招满了吗
ANEOY:今年感觉真是后端地狱级难度了,从暑期就是这样,前端需求非常大
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务