題目描述: n 個員工圍坐圓桌,每人有一個最喜歡的同事 favorite[i]。每人只願意坐在自己喜歡的同事旁邊。求最多能邀請多少人參加會議。
解題思路: 每個節點只有一條出邊,形成的圖是「函數圖」(functional graph)。這種圖由若干棵樹(樹根指向環中節點)和環組成。
答案是以下兩種情況的最大值:
情況 1:大環 找所有環中最大的環長度。整個圓桌就是這個環。
情況 2:多對互相喜歡的搭配 長度為 2 的環(互相喜歡的一對)可以各自帶上自己的「尾巴」(從外部指向它們的最長鏈)。多對這樣的組合可以同時坐在圓桌上(因為每對之間可以插入其他對)。
具體步驟:
時間複雜度: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 計算最長鏈。需要先找出所有環,再分別處理。適合環較少的情況。