HardRating 2419
1203. Sort Items by Groups Respecting Dependencies
depth-first-searchbreadth-first-searchgraphtopological-sort
解題說明
Sort Items by Groups Respecting Dependencies
題目描述: 有 n 個項目分成若干組(有些項目沒有分組,用 -1 表示)。給定項目間的依賴關係,要求排序所有項目,使得:(1) 同一組的項目相鄰 (2) 依賴關係被滿足。如果無法滿足,返回空陣列。
解題思路:
- 兩層拓撲排序:先對沒有分組的項目各自分配獨立的組。
- 組間拓撲排序:如果依賴跨組(項目 a 在組 X,依賴項目 b 在組 Y),則組 Y 必須排在組 X 前面。對組建立 DAG 並拓撲排序。
- 組內拓撲排序:對每個組內的項目,根據組內的依賴關係做拓撲排序。
- 按照組的拓撲序,依次輸出每組內的項目(也按拓撲序)。
- 如果任何一層拓撲排序發現環(無法完成排序),返回空陣列。
C++ 解法
複雜度分析
時間複雜度:O(n + m + E) — n 為項目數,m 為組數,E 為依賴邊數
空間複雜度:O(n + m + E) — 圖的鄰接表和拓撲排序的資料結構
虛擬碼
1. Assign unique group IDs to items with group == -1 2. Build item-level DAG and group-level DAG from dependencies 3. Remove duplicate edges in group graph 4. Topological sort on group-level DAG - If cycle detected: return empty array 5. For each group (in group topological order): - Topological sort items within the group - If cycle detected: return empty array - Append sorted items to result 6. Return result
其他解法
-
DFS 拓撲排序:用 DFS 代替 BFS(Kahn's algorithm)做拓撲排序。使用狀態標記(未訪問/處理中/已完成)來檢測環。效率相同但有些人覺得 DFS 版本更直覺。
-
合併為單層拓撲排序:將組的約束轉化為項目間的虛擬依賴邊,然後做一次拓撲排序。但這樣邊數可能大幅增加,且需要額外處理「同組相鄰」的約束。
延伸思考
- 如果組不是預先指定的,而是要你分組使得依賴能被滿足,如何設計?
- 如果要求輸出所有合法排序中字典序最小的呢?
- 如何處理循環依賴——是否能找出最少需要打破多少條邊?