2127.参加会议的最多员工数

链接：2127.参加会议的最多员工数
难度：Hard
标签：深度优先搜索、图、拓扑排序
简介：给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。

题解 1 - python

• 编辑时间：2023-11-01
• 执行用时：552ms
• 内存消耗：137.49MB
• 编程语言：python
• 解法介绍：判断环的数量，如果环内超过2个，找最大数量的环，如果只有2个，找两个点的最大延伸链。

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        deg = [0 for _ in range(n)]
        for i in range(n): deg[favorite[i]] += 1
        q = deque(i for i in range(n) if deg[i] == 0)
        nexts = [[] for _ in range(n)]
        while q:
            i = q.popleft()
            nexts[favorite[i]].append(i)
            deg[favorite[i]] -= 1
            if deg[favorite[i]] == 0: q.append(favorite[i])
        def dfs(idx: int) -> int:
            res = 1
            for next_i in nexts[idx]:
                res = max(res, dfs(next_i) + 1)
            return res
        max_ring = sum_chain = 0
        for i in range(n):
            if deg[i] == 0: continue
            deg[i] = 0
            ring = 1
            next_i = favorite[i]
            while next_i != i:
                deg[next_i] = 0
                ring += 1
                next_i = favorite[next_i]
            if ring == 2: sum_chain += dfs(i) + dfs(favorite[i])
            else: max_ring = max(max_ring, ring)
        return max(sum_chain, max_ring)