参加会议的最多员工数

难度: Hard

一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张圆形的桌子，可以坐下 任意数目 的员工。

员工编号为 0 到 n - 1 。每位员工都有一位喜欢的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工不会是他自己。

给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。

示例 1：

输入：favorite = [2,2,1,2]
输出：3
解释：
上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。
注意，公司也可以邀请员工 1，2 和 3 参加会议。
所以最多参加会议的员工数目为 3 。

示例 2：

输入：favorite = [1,2,0]
输出：3
解释：
每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。
座位安排同图 1 所示：
- 员工 0 坐在员工 2 和 1 之间。
- 员工 1 坐在员工 0 和 2 之间。
- 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。

示例 3：

输入：favorite = [3,0,1,4,1]
输出：4
解释：
上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。
员工 2 无法参加，因为他喜欢的员工 1 旁边的座位已经被占领了。
所以公司只能不邀请员工 2 。
参加会议的最多员工数目为 4 。

提示：

n == favorite.length
2 <= n <= 10⁵
0 <= favorite[i] <= n - 1
favorite[i] != i

Submission

运行时间: 163 ms

内存: 28.8 MB

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        deg = [0] * n
        for f in favorite:
            deg[f] += 1  # 统计基环树每个节点的入度

        max_depth = [1] * n
        q = deque(i for i, d in enumerate(deg) if d == 0)
        while q:  # 拓扑排序，剪掉图上所有树枝
            x = q.popleft()
            y = favorite[x]  # x 只有一条出边
            max_depth[y] = max_depth[x] + 1
            deg[y] -= 1
            if deg[y] == 0:
                q.append(y)

        max_ring_size = sum_chain_size = 0
        for i, d in enumerate(deg):
            if d == 0: continue

            # 遍历基环上的点
            deg[i] = 0  # 将基环上的点的入度标记为 0，避免重复访问
            ring_size = 1  # 基环长度
            x = favorite[i]
            while x != i:
                deg[x] = 0  # 将基环上的点的入度标记为 0，避免重复访问
                ring_size += 1
                x = favorite[x]

            if ring_size == 2:  # 基环长度为 2
                sum_chain_size += max_depth[i] + max_depth[favorite[i]]  # 累加两条最长链的长度
            else:
                max_ring_size = max(max_ring_size, ring_size)  # 取所有基环长度的最大值
        return max(max_ring_size, sum_chain_size)

Explain

本题解利用了图论中基环树（cactus）的概念，将问题转化为在有向图中找到最大的基环树的大小。首先，通过计算每个员工被喜欢的次数（即入度），可以识别并删除所有的树枝，这是通过拓扑排序实现的。在拓扑排序过程中，我们也计算了从每个树叶到其树根的最长路径长度。其次，对于残留在图中的环，我们需要特别处理长度为2的环，因为这种环可以利用其外部的链条来增加参与会议的人数。最后，比较由长度为2的环构成的链和最大环的大小，返回最大值，即为最多可能参加会议的员工数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        deg = [0] * n  # 统计每个节点的入度
        for f in favorite:
            deg[f] += 1

        max_depth = [1] * n
        q = deque(i for i, d in enumerate(deg) if d == 0)  # 入度为0的节点入队
        while q:  # 拓扑排序处理
            x = q.popleft()
            y = favorite[x]
            max_depth[y] = max(max_depth[x] + 1, max_depth[y])
            deg[y] -= 1
            if deg[y] == 0:
                q.append(y)

        max_ring_size = sum_chain_size = 0
        for i in range(n):
            if deg[i] == 0: continue  # 跳过已处理的节点

            # 处理环
            ring_size = 1
            x = i
            y = favorite[x]
            while y != i:
                x = y
                y = favorite[x]
                ring_size += 1
                deg[x] = 0  # 标记节点已访问

            if ring_size == 2:
                sum_chain_size += max_depth[i] + max_depth[favorite[i]]
            else:
                max_ring_size = max(max_ring_size, ring_size)

        return max(max_ring_size, sum_chain_size)  # 返回最大值

Explore

在拓扑排序的实现中，每个节点的入度被初始化并在遍历时逐步减少。当节点的入度变为0时，它会被加入到队列中，然后从队列中移除并处理。在处理过程中，该节点指向的下一个节点的入度会减1。如果这个下一个节点的入度也变为0，则会被加入队列。这个过程确保每个节点只有在其入度为0时才被访问一次，从而保证每个节点在整个拓扑排序过程中只被访问一次。

长度为2的环特别之处在于它们形成了相互喜欢的一对节点，即两个员工各自是对方的最喜欢的员工。在这种情况下，这两个员工可以被视为一个单独的小组，并且可以进一步延伸他们各自的入度为0的路径，增加参与会议的人数。这种配置使得从这对员工延伸出的路径的总长度可能超过其他任何单一环或链的长度，因此需要特别处理以最大化参与会议的员工数。

在处理长度为2的环时，每个节点i及其最喜欢的节点`favorite[i]`形成一个互相指向的环。`max_depth[i]`和`max_depth[favorite[i]]`分别表示从节点i和节点`favorite[i]`向外延伸到达任何一个入度为0的节点的最长路径长度。将这两个最长路径相加，就得到了从这个长度为2的环向外延伸的最长链的总长度，这是因为可以从环的任一节点向外延伸并返回，形成一个更长的参与链。

基环树是一种特殊的图结构，包含一个环和若干从环上的节点延伸出的树。在本题解中，通过拓扑排序首先移除所有入度为0的节点，即剥离出所有的树枝，只留下包含环的结构。然后，针对每个还存在的环，计算环的大小或者通过特殊规则增加由长度为2的环延伸的链的长度。最终，算法通过比较这些环和链的大小来找出可以参加会议的最多员工数。这种处理方式充分利用了基环树的特性，即环和树枝的结合，来优化问题的解决方案。