千问 LeetCode 2360.图中的最长环 public int longestCycle(int[] edges)

这道题的关键在于利用每个节点最多只有一条出边这个特殊性质这样图就由若干条链 环组成基环内向树。最优雅的解法是时间戳法一次遍历即可不需要拓扑排序或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推荐使用。