好的,这是 LeetCode 2360. 图中的最长环 的 JavaScript 实现,同样采用时间戳法,高效且简洁。

/**
 * @param {number[]} edges
 * @return {number}
 */
var longestCycle = function(edges) {
    const n = edges.length;
    const visitTime = new Array(n).fill(0); // 记录每个节点第一次被访问的时间戳
    let ans = -1;
    let time = 0; // 全局时间戳

    for (let i = 0; i < n; i++) {
        if (visitTime[i] !== 0) continue; // 已访问过,跳过

        const startTime = time; // 记录本轮开始的时间
        let 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. 时间戳数组:visitTime 初始化为 0,表示未访问。
2. 每轮遍历:从每个未访问的节点出发,沿着 edges 走,边走边记录时间戳。
3. 发现环的条件:当遇到一个节点 cur,它的 visitTime[cur] 不为 0,且大于本轮开始时间 startTime,说明这个节点是在本轮遍历中被访问过的,即构成了环。
4. 环长计算:time - visitTime[cur] + 1,其中 time 是当前时间戳(已自增到下一个未访问节点),visitTime[cur] 是环上节点的起始时间戳。

示例验证:

// 示例 1
edges = [3,3,4,2,3]
// 输出: 3
// 解释: 最长环 2 -> 4 -> 3 -> 2,长度为 3

// 示例 2
edges = [2,-1,3,1]
// 输出: -1
// 解释: 无环

复杂度分析:
- 时间复杂度:O(n),每个节点恰好被访问一次。
- 空间复杂度:O(n),用于 visitTime 数组。

另一种写法(使用 Map 记录本轮路径):

var longestCycle = function(edges) {
    const n = edges.length;
    const visited = new Array(n).fill(false);
    let ans = -1;

    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;

        const timeMap = new Map(); // 记录本轮路径中节点的时间
        let cur = i;
        let time = 0;

        while (cur !== -1 && !visited[cur]) {
            timeMap.set(cur, time++);
            visited[cur] = true;
            cur = edges[cur];
        }

        if (cur !== -1 && timeMap.has(cur)) {
            ans = Math.max(ans, time - timeMap.get(cur));
        }
    }

    return ans;
};

不过第一种时间戳法更省空间(只用数组,不用 Map),推荐使用。

 

更多推荐