6135. 图中的最长环

Difficulty
Hard
Tags
拓扑排序
图
URL
https://leetcode.cn/problems/longest-cycle-in-a-graph/
Star
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。
图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。
请你返回图中的 最长 环，如果没有任何环，请返回 -1 。
一个环指的是起点和终点是 同一个 节点的路径。
示例 1：
notion imagenotion image
输入：edges = [3,3,4,2,3]
输出去：3
解释：图中的最长环是：2 -> 4 -> 3 -> 2 。
这个环的长度为 3 ，所以返回 3 。
示例 2：
notion imagenotion image
输入：edges = [2,-1,3,1]
输出：-1
解释：图中没有任何环。
提示：
  • n == edges.length
  • 2 <= n <= 105
  • 1 <= edges[i] < n
  • edges[i] != i
通过次数3,404提交次数10,880

法1 拓扑排序 + BFS

思路
用拓扑排序 逐个移除入度为 0 的节点，然后剩下的节点必然是在 环 中的节点，
然后再用 BFS 找最大环。
notion imagenotion image
题解
class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        # 1. 拓扑排序 将入度为 0 的节点逐层删除
        in_degree = [0 for _ in edges]
        for i in range(0, len(edges)):
            if edges[i] != -1:
                in_degree[edges[i]] += 1
        
        queue = deque()
        for i in range(0, len(in_degree)):
            if in_degree[i] == 0:
                queue.append(i)

        # 移除的是 非环中的节点
        rested = set([i for i in range(len(in_degree))])

        while queue:
            cur_node = queue.pop()
            rested.remove(cur_node) # 移除该节点
            nxt_node = edges[cur_node]
            if nxt_node != -1:
                in_degree[nxt_node] -= 1
                if in_degree[nxt_node] == 0:
                    queue.append(nxt_node)
        
        # 2. 剩下的节点 就必定是环 （可能是多个环）
        # 然后依次遍历过去即可
        res = -1
        visited = set()
        for s_node in rested:
            if s_node not in visited:
                visited.add(s_node)
                n_node = edges[s_node]
                step = 1
                while n_node not in visited:
                    step += 1
                    visited.add(n_node)
                    n_node = edges[n_node]
                
                res = max(res, step) 
        
        return res