題目描述: 有 n 個項目分成若干組(有些項目沒有分組,用 -1 表示)。給定項目間的依賴關係,要求排序所有項目,使得:(1) 同一組的項目相鄰 (2) 依賴關係被滿足。如果無法滿足,返回空陣列。
解題思路:
時間複雜度: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 版本更直覺。
合併為單層拓撲排序:將組的約束轉化為項目間的虛擬依賴邊,然後做一次拓撲排序。但這樣邊數可能大幅增加,且需要額外處理「同組相鄰」的約束。