今日问题

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)