HardRating 2449
2127. Maximum Employees to Be Invited to a Meeting
arraydynamic-programmingdepth-first-searchgraphtopological-sort
解題說明
Maximum Employees to Be Invited to a Meeting
題目描述： n 個員工圍坐圓桌，每人有一個最喜歡的同事 favorite[i]。每人只願意坐在自己喜歡的同事旁邊。求最多能邀請多少人參加會議。
解題思路： 每個節點只有一條出邊，形成的圖是「函數圖」（functional graph）。這種圖由若干棵樹（樹根指向環中節點）和環組成。
答案是以下兩種情況的最大值：
情況 1：大環 找所有環中最大的環長度。整個圓桌就是這個環。
情況 2：多對互相喜歡的搭配 長度為 2 的環（互相喜歡的一對）可以各自帶上自己的「尾巴」（從外部指向它們的最長鏈）。多對這樣的組合可以同時坐在圓桌上（因為每對之間可以插入其他對）。
具體步驟：
- 用拓撲排序剝離所有不在環上的節點，同時計算每個節點的最長入鏈長度。
- 找出所有環。對長度 > 2 的環取最大值。
- 對長度 == 2 的環，加上兩端的最長鏈長度。所有這些雙人組的總和作為情況 2 的候選。
- 答案 = max(最大環, 所有雙人組總和)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 拓撲排序 O(n)，環偵測 O(n)，每個節點只處理一次。
空間複雜度：O(n) — 入度陣列和深度陣列各 O(n)。
虛擬碼
1. Compute in-degree for each node. 2. Topological sort: process nodes with in-degree 0, compute depth[v] = max chain length ending at v. 3. Remaining nodes are in cycles. For each unvisited cycle: a. Trace the cycle, count its length. b. If length == 2: pairSum += depth[node1] + depth[node2]. c. If length > 2: maxCycle = max(maxCycle, length). 4. Return max(maxCycle, pairSum).
其他解法
-
DFS 環偵測法：用 DFS 搭配顏色標記（白/灰/黑）找環，灰色節點形成環。對每個環外節點做 DFS 計算最長路徑。時間複雜度相同 O(n)，但實作較拓撲排序複雜。
-
反向圖 BFS：建立反向圖（誰喜歡我），從環上節點出發做 BFS 計算最長鏈。需要先找出所有環，再分別處理。適合環較少的情況。
延伸思考
- 若每個人可以有 K 個喜歡的同事（不只 1 個），圖結構會如何變化？問題的難度會增加到什麼程度？
- 若圓桌有容量限制（最多 M 個座位），如何修改演算法選擇最優子集？
- 若需要最小化未被邀請的人中「最喜歡的人被邀請了」的數量（最小嫉妒），如何建模？