)
这道题的关键在于利用每个节点最多只有一条出边这个特殊性质，这样图就由若干条链 + 环组成（基环内向树）。
最优雅的解法是时间戳法，一次遍历即可，不需要拓扑排序或DFS递归。
Java 实现：
class Solution {
public int longestCycle(int[] edges) {
int n = edges.length;
int[] visitTime = new int[n]; // 记录每个节点第一次被访问的时间戳
int ans = -1;
int time = 0; // 全局时间戳
for (int i = 0; i < n; i++) {
if (visitTime[i] != 0) continue; // 已访问过，跳过
int startTime = time; // 记录本轮开始的时间
int cur = i;
while (cur != -1 && visitTime[cur] == 0) {
visitTime[cur] = ++time; // 记录访问时间
cur = edges[cur];
}
// 如果停在了本轮访问过的节点上，说明发现了环
if (cur != -1 && visitTime[cur] > startTime) {
ans = Math.max(ans, time - visitTime[cur] + 1);
}
}
return ans;
}
}
核心思路：
1. 时间戳思想：用一个全局 time 变量，每访问一个新节点就 ++time 并记录。
2. 每轮遍历：从每个未访问的节点出发，沿着 edges 一直走，直到：
- 遇到 -1（无出边）→ 终止
- 遇到之前已经访问过的节点 → 终止
- 遇到本轮才访问过的节点 → 发现环！
3. 环长计算：当前时间 - 环上节点的访问时间 + 1
示例图解：
edges = [3,3,4,2,3]
节点: 0 → 3 → 2 → 4 → 3（回到3，发现环）
时间: 1 2 3 4 5
环长 = 5 - 2 + 1 = 4？不对，仔细看：
实际上路径是：0→3(时间2) → 3→2(时间3) → 2→4(时间4) → 4→3(时间5)
当走到 3 时发现 visitTime[3]=2，且 2 > startTime(1)，说明是环。
环长 = 5 - 2 + 1 = 4？不对，2→4→3 才是环，长度是 3。
所以公式是：环长 = 当前时间 - 环上节点的访问时间（不需要 +1）
修正后：
if (cur != -1 && visitTime[cur] > startTime) {
ans = Math.max(ans, time - visitTime[cur] + 1);
}
复杂度：
- 时间复杂度：O(n)，每个节点只访问一次
- 空间复杂度：O(n)，用于 visitTime 数组
另一种写法（更直观，用布尔数组标记）：
class Solution {
public int longestCycle(int[] edges) {
int n = edges.length;
boolean[] visited = new boolean[n];
int ans = -1;
for (int i = 0; i timeMap = new HashMap();
int cur = i;
int time = 0;
while (cur != -1 && !visited[cur]) {
timeMap.put(cur, time++);
visited[cur] = true;
cur = edges[cur];
}
if (cur != -1 && timeMap.containsKey(cur)) {
ans = Math.max(ans, time - timeMap.get(cur));
}
}
return ans;
}
}
不过第一种时间戳法更省空间（只用数组，不用Map），推荐使用。
