leetcode: 6135. The longest ring in the graph [inward base ring tree + longest ring board + timestamp]

Analysis

The out-degree of each point is at most 1
So it is a [weakened] inward basis ring graph
All connected components have at most one ring
All points have at most one ring
The way of using timestampRecord the time of the last visit of each point
If there are repeated visits and the start time is after st, it means a new ring
Record it in the record
At the same time update the timestamp, and this pointThe most recent timestamp is sufficient

ac code

class Solution:def longestCycle(self, edges: List[int]) -> int:# At most one outgoing edge -> weaken the inward base ring tree# Each Unicom component has at most one ring# Each point has at most one ring# Timestamp + optimization while traversingn = len(edges)time = [0] * nclock, ans = 1, -1# x is the starting pointfor x, t in enumerate(time):if t: continue # has been passively traversed beforest = clockwhile x >= 0:if time[x]: # Second traversal xif time[x] >= st: # find a new ringans = max(ans, clock - time[x])breaktime[x] = clockclock += 1x = edges[x]return ans

Summary

Graph Theory + Max Ring + Inward Basis Ring + Timestamp