2020牛客寒假算法基础集训营6.B——图【基环树 & 记忆化dfs】

​​题目传送门​​

题目描述

现在有一个N个点的有向图，每个点仅有一条出边 你需要求出图中最长的简单路径包含点的数量 （1≤N≤1,000,000）

输入描述:

第一行一个数字N 接下来N行，每行一个正整数，第i+1行的数字表示第i个点出边终点的编号 （点从1开始标号）

输出描述:

一行一个数字，最长的简单路径的长度

输入

3 2 3 2

输出

3

题解

AC-Code

#include using namespace std;typedef long long ll;#defineconst int maxn = 1e6 + 7;const int mod = 1e9 + 7;int to[maxn];int vis[maxn];int ans[maxn];int dfs(int now) { vis[now] = 1; if (vis[to[now]]) { // 下一个点 走过 if (ans[to[now]]) { // 同一条路径先算子节点。如果>1说明不是一条路径 ans[now] = ans[to[now]] + 1; } else { // 走到环 int t = now, num = 1; while (to[t] != now) { // 走一圈环，记录环的长度 t = to[t]; ++num; } ans[now] = num; t = now; while (to[t] != now) { // 再走一遍环，更新环上点的答案 t = to[t]; ans[t] = num; } } } else { dfs(to[now]); if (!ans[now]) ans[now] = ans[to[now]] + 1; } return ans[now];}int main() { ios; int n; while (cin >> n) { memset(vis, 0, sizeof vis); memset(ans, 0, sizeof ans); for (int i = 1; i <= n; ++i) cin >> to[i]; int ans = 0; for (int i = 1; i <= n; ++i) { if (!vis[i]) ans = max(ans, dfs(i)); } cout << ans << endl; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。