# 原题为LeetCode2360. 图中的最长环
# 链接：https://leetcode.cn/problems/longest-cycle-in-a-graph/
# 最大的收获：list.pop(0) 会比 list.pop() 更耗时间，然后就卡常了
# 顺便复习了一下并查集

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        # 拓扑排序复习课堂开课了！
        # 第三版《算法导论》有亿点难看，finishing times指的原来是入度啊

        # 日常变量初始化
        n = len(edges)
        vis = set()
        queue = []
        cnt = n - 0
        ans = -1
        res = 0

        # 拓扑排序开课了！
        # 先统计所有边的入度（finishing times），然后找出所有入度为0的点进行初始化
        incnt = [0] * (n)
        for i in edges:             # 统计入度
            if i == -1 : continue   # 注意Python在索引为 -1 时不会报错
            incnt[i] += 1
        for i in range(n):
            if incnt[i] == 0:
                queue.append(i)

        # 拓扑排序正式部分
        # 从所有入度为0（只有出边，是起点）的点开始遍历
        # 过河拆桥制，每遍历一条边就删除一点入度
        # 当所有的边都被删了，就是说这点变成起点了
        # 每个点入度变成0的顺序就是该点在拓扑排序中的排序顺序
        # 拓扑排序的机制：对于一个有向无环图，所有边的朝向都是从较前结点指向较厚结点
        # 拓扑排序判断环：由于环上的每个点都至少有一点入度，所以全图排序后不可能入度全为0
        #   （即：若拓扑排序中发现前向边(u,v)，在遍历过的点中一定存在一条路径，等价于(v,u)）
        while len(queue) > 0:
            # 如果需要记录拓扑排序，可以在这时记录拓扑排序顺序
            u = queue.pop()    
            v = edges[u]
            if v == -1:         # 能遍历到的点都是起点
                continue        # 没有出度的明显是终点
            incnt[v] -= 1       # 扣除一点入度
            if incnt[v] == 0:   # 发现一个新的起点
                queue.append(v)

        # 这里是拓扑排序找环，所以如果入度全部为0就是没有环
        if max(incnt) == 0:
            return -1

        # -----------------------------------------------
        # 【单纯的dfs求长度】           320 ms  32.3 MB
        # 还以为是这里卡常了，后来发现并非如此
        # 剩下的入度非0结点肯定在环上，只需要对这些点进行查询即可
        # 因为所有点只有一条出边，所以就偷懒了
        for st in range(n):
            if st in vis : continue
            if incnt[st] == 0: continue
            res = 0
            cur = st
            while True:
                if cur in vis : break
                vis.add(cur)
                res = res + 1
                cur = edges[cur]
            if res > ans:
                ans = res
        return ans

        # -----------------------------------------------
        # 【并查集解法】                692 ms 42.3 MB
        # 甚至还比普通解法慢，可能是因为每个点只有一条出边

        # 并查集初始化
        lovelive = [0] * (n)    # 各节点的父亲节点
        tokimeki = [1] * (n)    # 各并查集的数量和
        for i in range(n):
            lovelive[i] = i     # 初始父亲节点就是自己

        # 并查集查询函数
        def getFather(i):
            if lovelive[i] == i : return i
            fa = getFather(lovelive[i])
            # tokimeki[fa] += tokimeki[i]
            lovelive[i] = fa
            return lovelive[i]

        def mergeDD(a,b):
            fa = getFather(a)
            fb = getFather(b)
            if fa == fb : return
            tokimeki[fa] += tokimeki[fb]
            lovelive[fb] = fa

        for i in range(n):
            if incnt[i] == 0: continue
            mergeDD(i,edges[i])

        for i in range(n):
            ans = max(ans,tokimeki[i])

        #print (tokimeki,lovelive)
        return ans

    # 屑屑你，超时了
    def longestCycle_TLE(self, edges: List[int]) -> int:
        # 屑屑你，竟然可以不是强联通分量求环
        n = len(edges)
        ans = -1
        vis = set()
        for i in range(0,n):
            s = []
            if i in vis : continue
            cur = i
            res = 0
            while cur != -1 and (not cur in s):
                s.append(cur)
                vis.add(cur)
                cur = edges[cur]
            if cur == -1 : continue
            while s[0] != cur:
                s.pop(0)
            if len(s) > ans:
                ans = len(s)
        return ans