php 解法, 执行用时: 304 ms, 内存消耗: 31.9 MB, 提交时间: 2023-09-14 09:50:17

class Solution {

    /**
     * @param Integer[] $edges
     * @return Integer
     */
    function longestCycle($edges) {
    	$time = array_fill(0, count($edges), 0);
    	$ans = -1;
        for ($i = 0, $clock = 1; $i < count($edges); $i++) {
            if ($time[$i]) continue;
            for ($x = $i, $start_time = $clock; $x >= 0; $x = $edges[$x]) {
                if ($time[$x]) { // 重复访问
                    if ($time[$x] >= $start_time) // 找到了一个新的环
                        $ans = max($ans, $clock - $time[$x]);
                    break;
                }
                $time[$x] = $clock++;
            }
        }
        return $ans;
    }
}

golang 解法, 执行用时: 136 ms, 内存消耗: 9.4 MB, 提交时间: 2023-09-14 09:39:34

func longestCycle(edges []int) int {
	time := make([]int, len(edges))
	clock, ans := 1, -1
	for x, t := range time {
		if t > 0 {
			continue
		}
		for startTime := clock; x >= 0; x = edges[x] {
			if time[x] > 0 { // 重复访问
				if time[x] >= startTime { // 找到了一个新的环
					ans = max(ans, clock-time[x])
				}
				break
			}
			time[x] = clock
			clock++
		}
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 128 ms, 内存消耗: 85.1 MB, 提交时间: 2023-09-14 09:39:13

class Solution {
public:
    int longestCycle(vector<int> &edges) {
        int n = edges.size(), time[n], ans = -1;
        memset(time, 0, sizeof(time));
        for (int i = 0, clock = 1; i < n; ++i) {
            if (time[i]) continue;
            for (int x = i, start_time = clock; x >= 0; x = edges[x]) {
                if (time[x]) { // 重复访问
                    if (time[x] >= start_time) // 找到了一个新的环
                        ans = max(ans, clock - time[x]);
                    break;
                }
                time[x] = clock++;
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 9 ms, 内存消耗: 55.8 MB, 提交时间: 2023-09-14 09:38:35

class Solution {
    public int longestCycle(int[] edges) {
        /*
        基环树+时间戳
        times[i]记录首次访问编号为i的节点时间点，clock维护当前的时间节点
        我们枚举每个出发点
        1.遇到之前访问过的节点times[i]>0，跳过
        2.首次访问节点i，从节点i出发向前走同时标记访问过的节点的时间戳
        如果前方出现过times[j]>0的情况说明这个时候节点已经被访问过，说明成环了
        注意:为了避免后面枚举的节点重复经过之前访问过的节点但是不成环的情况，要加一个判断条件times[j]>=start
        其中start为从i点出发的时间戳，若成环必然有times[j]>=start，重复经过旧节点但是不成环的情况是times[j]<start
        因为你这个times[j]之前一轮出发点中已经枚举过了，时间必定在该轮start之前
        维护这个环的长度最大值就是答案
        时间复杂度:O(N) 空间复杂度:O(N)
         */
        int res = -1;
        int n = edges.length;
        int[] times = new int[n];
        // 枚举每个出发点
        for (int i = 0, clock = 1; i < n; i++) {
            if (times[i] > 0) continue; // 这个出发点已经访问过了，跳过
            int start = clock;  // start维护当前出发点的出发时间
            // 枚举以节点i为出发点的路径上的点
            for (int x = i; x != -1; x = edges[x]) {
                if (times[x] > 0) { // 已经访问过该节点(不一定是该轮的)
                    // 若该节点是该轮才访问的说明成环了
                    if(times[x] >= start) res = Math.max(res, clock - times[x]);  // 维护最大环值
                    break;  // 已经访问过节点就退出，不论是该轮访问的还是之前
                }
                times[x] = clock++; // 标记访问该节点的最早时间戳
            }
        }
        return res;
    }
}

python3 解法, 执行用时: 256 ms, 内存消耗: 28.2 MB, 提交时间: 2023-09-14 09:37:27

# 内向基环树找环+时间戳
class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        time = [0] * len(edges)
        clock, ans = 1, -1
        for x, t in enumerate(time):
            if t: continue  # 非指向0
            start_time = clock
            while x >= 0:
                if time[x]:  # 重复访问
                    if time[x] >= start_time:  # 找到了一个新的环
                        ans = max(ans, clock - time[x])
                    break
                time[x] = clock
                clock += 1
                x = edges[x]
        return ans