给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。
图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。
如果节点 i 没有出边，那么 edges[i] == -1 。
1. 深度优先搜索
同时记录已遍历的进行剪枝
class Solution {
public:
int longestCycle(vector<int>& edges) {
int res = -1;
int n = edges.size();
vector<int> pathval(n);
for(int i=0;i<n;i++){//遍历所有节点找环
if(edges[i]<0) continue;//没有出边，或已经遍历过
int cur = i; int val = 1;
vector<int> visit;
while(cur>=0){//递归到没有下一个顶点
visit.push_back(cur);//加入已遍历节点中
if(edges[cur]<0) break;//下一节点已遍历，跳出循环，剪枝
if(pathval[cur]>0){
res = max(res,val-pathval[cur]);//计算环的长度
break;//这次循环遍历过
}
pathval[cur] = val;//顶点赋权值
val++;//权值增加
cur= edges[cur];//移动到下一节点
}
for(int index:visit)
edges[index] = -1;//将已遍历的置为-1
}
return res;
}
};
2. 更优雅的写法
运用全局时间戳，减少判断
class Solution {
public:
int longestCycle(vector<int> &edges) {
int n = edges.size();
int res = -1;
vector<int> time(n);
for (int i = 0, clock = 1; i < n; i++) {//遍历n个顶点
if (time[i]) continue; //已经遍历过跳过
for (int x = i, start_time = clock; x >= 0; x = edges[x]) {//递归到没有下一个顶点
if (time[x]) { // 重复访问
if (time[x] >= start_time) // 找到了一个新的环，关键语句，全局时间戳，避免将原来遍历过的视为环
res = max(res, clock - time[x]);
break;
}
time[x] = clock++;//标记
}
}
return res;
}
};