今日题目

https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/description/

解题思路

本题给出一个有向图，其中包含环。为了找出环，可以使用拓扑排序：找出入度为 0 的节点，并将其及其对应的边删除。

这样处理后，图中剩余的节点都处于环内。

本题中，有两种方式让所有人入座：

  1. 一个完整的环，环中每个人的左手边坐着自己最喜欢的人。
  2. 当两个人互相是对方最喜欢的人时，他们两人本身就构成一个完整的环，而喜欢他们的人可以形成一条链指向他们。这种结构比较特殊，因为每个人都能找到自己最喜欢的人，而无需构成完整的环。因此，会议室中可以同时存在多个这样的结构。

算法步骤

  1. 使用拓扑排序找出图中所有的环。
  2. 找出所有两人互为最喜欢的特殊情况。
  3. 返回单个最大环的大小，或返回多个特殊结构的总大小，取两者的最大值。

复杂度分析

  • 时间复杂度：$O(N)$

  • 空间复杂度：$O(N)$

代码

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        N = len(favorite)
        du = [0] * N
        l = [1] * N
        for x in favorite:
            du[x] += 1

        q = deque([])
        for i in range(N):
            if du[i] == 0:
                q.append((i, 1))
        
        while(len(q) > 0):
            x, leng = q.popleft()
            to = favorite[x]
            du[to] -= 1
            l[to] = max(l[to], leng + 1)
            if du[to] == 0:
                q.append((to, leng + 1))
        
        vis = [0] * N

        def dfs(i):
            to = favorite[i]
            vis[i] = 2
            if vis[to] == 2:
                return 1
            return dfs(to) + 1

        ans = 0
        res = 0
        for i in range(N):
            if du[i] != 0 and vis[i] == 0:
                tmp = dfs(i)
                # print(i, tmp)
                if tmp == 2:
                    # print(i, favorite[i], l[i], l[favorite[i]])
                    res += l[i] + l[favorite[i]]

                else:
                    ans = max(ans, tmp)
        
        return max(ans, res)