HardRating 2419

1203. Sort Items by Groups Respecting Dependencies

depth-first-searchbreadth-first-searchgraphtopological-sort

在 LeetCode 上作答 ↗

解題說明

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 版本更直覺。
合併為單層拓撲排序：將組的約束轉化為項目間的虛擬依賴邊，然後做一次拓撲排序。但這樣邊數可能大幅增加，且需要額外處理「同組相鄰」的約束。

延伸思考

如果組不是預先指定的，而是要你分組使得依賴能被滿足，如何設計？
如果要求輸出所有合法排序中字典序最小的呢？
如何處理循環依賴——是否能找出最少需要打破多少條邊？

Sort Items by Groups Respecting Dependencies — CaffeCode