2127. 可以被邀请参加会议的最多员工数

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 旁边的两个位置都被占了。
所以公司让他们退出会议。
可以被邀请参加会议的最多员工数是 4。

提示：

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

解题思路

这是一道复杂的图论题目。根据题目描述，我们需要理解员工关系形成的图的结构特点。

核心思路分析：

从 favorite 数组可以构建一个有向图，其中每个员工都恰好有一条出边指向他最喜欢的人。由于每个节点的出度都是1，这样的图必然由若干个连通分量组成，每个连通分量包含一个环和若干条指向环的链。

两种邀请方案：

选择一个长度≥3的环：只能邀请环上的员工，因为环外的员工无法同时满足与环内员工相邻的条件。
选择多个长度为2的环及其附属链：
- 长度为2的环意味着两个员工互相喜欢
- 可以将多个这样的"双人组"连同指向他们的链一起邀请
- 对于每个双人组，还可以包括指向这两人的最长链

算法步骤：

找出图中所有的环
对于长度≥3的环，记录最大环长度
对于长度为2的环，计算每个环连同其附属链的总长度
返回两种方案的最大值

复杂度考虑： 需要使用DFS找环，并计算链的最大深度。时间复杂度为O(n)，空间复杂度为O(n)。

代码实现

class Solution {
public:
    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        vector<vector<int>> reverse_graph(n);
        vector<int> visited(n, 0); // 0: unvisited, 1: visiting, 2: visited
        
        // Build reverse graph
        for (int i = 0; i < n; i++) {
            reverse_graph[favorite[i]].push_back(i);
        }
        
        // Find max cycle length >= 3
        int max_cycle = 0;
        
        // Find sum of all 2-cycles with their chains
        int sum_two_cycles = 0;
        vector<bool> in_two_cycle(n, false);
        
        function<int(int)> find_cycle = [&](int start) -> int {
            vector<int> path;
            unordered_set<int> in_path;
            int curr = start;
            
            while (visited[curr] == 0) {
                visited[curr] = 1;
                path.push_back(curr);
                in_path.insert(curr);
                curr = favorite[curr];
            }
            
            if (visited[curr] == 1) { // Found cycle
                int cycle_start_idx = 0;
                while (path[cycle_start_idx] != curr) cycle_start_idx++;
                
                int cycle_len = path.size() - cycle_start_idx;
                
                if (cycle_len == 2) {
                    // Mark nodes in 2-cycle
                    in_two_cycle[path[cycle_start_idx]] = true;
                    in_two_cycle[path[cycle_start_idx + 1]] = true;
                } else {
                    max_cycle = max(max_cycle, cycle_len);
                }
                
                return cycle_len;
            }
            
            return 0;
        };
        
        function<int(int, int)> dfs_max_depth = [&](int node, int avoid) -> int {
            int max_depth = 0;
            for (int neighbor : reverse_graph[node]) {
                if (neighbor != avoid && !in_two_cycle[neighbor]) {
                    max_depth = max(max_depth, 1 + dfs_max_depth(neighbor, avoid));
                }
            }
            return max_depth;
        };
        
        // Find all cycles
        for (int i = 0; i < n; i++) {
            if (visited[i] == 0) {
                find_cycle(i);
            }
        }
        
        // Calculate sum for 2-cycles with their chains
        vector<bool> processed(n, false);
        for (int i = 0; i < n; i++) {
            if (in_two_cycle[i] && !processed[i]) {
                int partner = favorite[i];
                processed[i] = processed[partner] = true;
                
                int chain1 = dfs_max_depth(i, partner);
                int chain2 = dfs_max_depth(partner, i);
                sum_two_cycles += 2 + chain1 + chain2;
            }
        }
        
        return max(max_cycle, sum_two_cycles);
    }
};

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        reverse_graph = [[] for _ in range(n)]
        visited = [0] * n  # 0: unvisited, 1: visiting, 2: visited
        
        # Build reverse graph
        for i in range(n):
            reverse_graph[favorite[i]].append(i)
        
        max_cycle = 0
        sum_two_cycles = 0
        in_two_cycle = [False] * n
        
        def find_cycle(start):
            nonlocal max_cycle
            path = []
            in_path = set()
            curr = start
            
            while visited[curr] == 0:
                visited[curr] = 1
                path.append(curr)
                in_path.add(curr)
                curr = favorite[curr]
            
            if visited[curr] == 1:  # Found cycle
                cycle_start_idx = path.index(curr)
                cycle_len = len(path) - cycle_start_idx
                
                if cycle_len == 2:
                    in_two_cycle[path[cycle_start_idx]] = True
                    in_two_cycle[path[cycle_start_idx + 1]] = True
                else:
                    max_cycle = max(max_cycle, cycle_len)
                
                return cycle_len
            return 0
        
        def dfs_max_depth(node, avoid):
            max_depth = 0
            for neighbor in reverse_graph[node]:
                if neighbor != avoid and not in_two_cycle[neighbor]:
                    max_depth = max(max_depth, 1 + dfs_max_depth(neighbor, avoid))
            return max_depth
        
        # Find all cycles
        for i in range(n):
            if visited[i] == 0:
                find_cycle(i)
        
        # Calculate sum for 2-cycles with their chains
        processed = [False] * n
        for i in range(n):
            if in_two_cycle[i] and not processed[i]:
                partner = favorite[i]
                processed[i] = processed[partner] = True
                
                chain1 = dfs_max_depth(i, partner)
                chain2 = dfs_max_depth(partner, i)
                sum_two_cycles += 2 + chain1 + chain2
        
        return max(max_cycle, sum_two_cycles)

public class Solution {
    public int MaximumInvitations(int[] favorite) {
        int n = favorite.Length;
        List<int>[] reverseGraph = new List<int>[n];
        int[] visited = new int[n]; // 0: unvisited, 1: visiting, 2: visited
        
        for (int i = 0; i < n; i++) {
            reverseGraph[i] = new List<int>();
        }
        
        // Build reverse graph
        for (int i = 0; i < n; i++) {
            reverseGraph[favorite[i]].Add(i);
        }
        
        int maxCycle = 0;
        int sumTwoCycles = 0;
        bool[] inTwoCycle = new bool[n];
        
        int FindCycle(int start) {
            List<int> path = new List<int>();
            HashSet<int> inPath = new HashSet<int>();
            int curr = start;
            
            while (visited[curr] == 0) {
                visited[curr] = 1;
                path.Add(curr);
                inPath.Add(curr);
                curr = favorite[curr];
            }
            
            if (visited[curr] == 1) { // Found cycle
                int cycleStartIdx = path.IndexOf(curr);
                int cycleLen = path.Count - cycleStartIdx;
                
                if (cycleLen == 2) {
                    inTwoCycle[path[cycleStartIdx]] = true;
                    inTwoCycle[path[cycleStartIdx + 1]] = true;
                } else {
                    maxCycle = Math.Max(maxCycle, cycleLen);
                }
                
                return cycleLen;
            }
            return 0;
        }
        
        int DfsMaxDepth(int node, int avoid) {
            int maxDepth = 0;
            foreach (int neighbor in reverseGraph[node]) {
                if (neighbor != avoid && !inTwoCycle[neighbor]) {
                    maxDepth = Math.Max(maxDepth, 1 + DfsMaxDepth(neighbor, avoid));
                }
            }
            return maxDepth;
        }
        
        // Find all cycles
        for (int i = 0; i < n; i++) {
            if (visited[i] == 0) {
                FindCycle(i);
            }
        }
        
        // Calculate sum for 2-cycles with their chains
        bool[] processed = new bool[n];
        for (int i = 0; i < n; i++) {
            if (inTwoCycle[i] && !processed[i]) {
                int partner = favorite[i];
                processed[i] = processed[partner] = true;
                
                int chain1 = DfsMaxDepth(i, partner);
                int chain2 = DfsMaxDepth(partner, i);
                sumTwoCycles += 2 + chain1 + chain2;
            }
        }
        
        return Math.Max(maxCycle, sumTwoCycles);
    }
}

var maximumInvitations = function(favorite) {
    const n = favorite.length;
    const reverseGraph = Array(n).fill(null).map(() => []);
    const visited = Array(n).fill(0); // 0: unvisited, 1: visiting, 2: visited
    
    // Build reverse graph
    for (let i = 0; i < n; i++) {
        reverseGraph[favorite[i]].push(i);
    }
    
    let maxCycle = 0;
    let sumTwoCycles = 0;
    const inTwoCycle = Array(n).fill(false);
    
    function findCycle(start) {
        const path = [];
        const inPath = new Set();
        let curr = start;
        
        while (visited[curr]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目