首页 > 图
开通博客写题解
头像 一Wa哇一天
发表于 2020-02-17 13:01:28
题目链接：图 时间限制： C/C++ 1秒，其他语言2秒空间限制： C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述现在有一个N个点的有向图，每个点仅有一条出边你需要求出图中最长的简单路径包含点的数量（1≤N≤1,000,000）输入描述:第一行一 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Bernard5
发表于 2021-01-31 18:01:59
tarjan做法显然是违背出题人意图的。 本题限制了每个点只有一条出边，所以不存在复杂回路，如果成环，只存在简单环。 于是可以直接DFS，如果成环，就把整个回路都置为回路上点的数量。 #include <bits/stdc++.h> #define sc(x) scanf("%lld" 展开全文
去ta的博客 赞 (0) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”