题目描述
现在有一个N个点的有向图，每个点仅有一条出边
你需要求出图中最长的简单路径包含点的数量
（1≤N≤1,000,000）
知识：每个点出度都为1的有向图是一个基环内向树森林，从一个点出发，沿着出边一路走下去，一定会走到一个环。
思路：简单的来说就是找环，然后递归更新最长路。
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> #define ll long long using namespace std; const int maxn = 1e6 + 100; const int mod = 1e9 + 7; int vis[maxn],to[maxn],ans[maxn],res; // vis[i] 表示 i 节点是否访问过，to[i] 表示下一个节点，ans[i] 维护当前节点的最大长度 void dfs(int x) { vis[x] = 1; // 标记走过 if(vis[to[x]]){ // 如果下个点已经访问过，也就是形成环了 if(!ans[to[x]]){ // 如果下一个节点的答案没有记录，就更新环内每一个点成环的长度 int cur = x;int num = 1; // num 环的长度 while(to[cur] != x){ // 环的长度 cur = to[cur];num++; } cur = x;ans[x] = num; while(to[cur] != x){ // 更新环内每个节点的值 cur = to[cur]; ans[cur] = num; } res = max(res,ans[x]); // 维护最大答案 }else{ // 递归返回路径更新当前节点的最大长度 ans[x] = ans[to[x]] + 1; } }else{ dfs(to[x]); if(!ans[x]) ans[x] = ans[to[x]] + 1; // 递归返回路径更新当前节点的最大长度 } res = max(res,ans[x]); } int main() { int n;scanf("%d",&n); for(int i = 1; i <= n;i++){ int x;scanf("%d",&x); to[i] = x; } for(int i = 1;i <= n;i++){ if(!vis[i]) dfs(i); } printf("%d ",res); return 0; }