1203. 按照组和依赖关系排序项目

Hard

题目描述

有 n 个项目，每个项目属于零个或一个组，其中 group[i] 是第 i 个项目所属的组，如果第 i 个项目不属于任何组，则等于 -1。项目和组都是从零开始索引的。一个组可以没有项目属于它。

返回项目的排序列表，使得：

属于同一组的项目在排序列表中彼此相邻。
这些项目之间存在一些关系，其中 beforeItems[i] 是一个列表，包含应该在排序数组中第 i 个项目之前的所有项目（在第 i 个项目的左侧）。

如果有多个解决方案，返回任何一个解决方案；如果没有解决方案，返回空列表。

示例 1：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]

示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：这与示例 1 相同，除了 4 需要在排序列表中位于 6 之前。

约束条件：

1 <= m <= n <= 3 * 10^4
group.length == beforeItems.length == n
-1 <= group[i] <= m - 1
0 <= beforeItems[i].length <= n - 1
0 <= beforeItems[i][j] <= n - 1
i != beforeItems[i][j]
beforeItems[i] 不包含重复元素

解题思路

这是一道复杂的拓扑排序问题，需要分层处理：

核心思路：

双层拓扑排序：首先对组进行拓扑排序，然后对每个组内的项目进行拓扑排序
预处理分组：为没有分组的项目（group[i] = -1）创建独立的组
构建依赖图：分别构建组间依赖图和组内项目依赖图

具体步骤：

重新分配组号：为 group[i] = -1 的项目分配新的组号
构建组间依赖关系：如果项目 a 依赖项目 b 且它们属于不同组，则组A依赖组B
构建组内依赖关系：如果项目 a 依赖项目 b 且它们属于同一组，则在组内建立依赖
对组进行拓扑排序：确定组的处理顺序
对每个组内的项目进行拓扑排序
按组的顺序合并结果

关键点：

需要检测组间和组内的循环依赖
使用 Kahn 算法（基于入度的拓扑排序）
任何一层出现环就返回空结果

代码实现

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        // 为没有组的项目分配新组号
        int groupId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = groupId++;
            }
        }
        
        // 构建组间和组内依赖图
        vector<vector<int>> groupGraph(groupId);
        vector<int> groupIndegree(groupId, 0);
        vector<vector<int>> itemGraph(n);
        vector<int> itemIndegree(n, 0);
        
        for (int i = 0; i < n; i++) {
            for (int prev : beforeItems[i]) {
                if (group[prev] != group[i]) {
                    // 不同组间的依赖
                    groupGraph[group[prev]].push_back(group[i]);
                    groupIndegree[group[i]]++;
                } else {
                    // 同组内的依赖
                    itemGraph[prev].push_back(i);
                    itemIndegree[i]++;
                }
            }
        }
        
        // 对组进行拓扑排序
        vector<int> groupOrder = topologicalSort(groupGraph, groupIndegree);
        if (groupOrder.size() != groupId) return {};
        
        // 对每个组内的项目进行拓扑排序
        unordered_map<int, vector<int>> groupToItems;
        for (int i = 0; i < n; i++) {
            groupToItems[group[i]].push_back(i);
        }
        
        vector<int> result;
        for (int g : groupOrder) {
            auto& items = groupToItems[g];
            if (items.empty()) continue;
            
            // 构建该组的子图
            vector<vector<int>> subGraph(n);
            vector<int> subIndegree(n, 0);
            for (int item : items) {
                for (int next : itemGraph[item]) {
                    subGraph[item].push_back(next);
                    subIndegree[next]++;
                }
            }
            
            vector<int> itemOrder = topologicalSort(subGraph, subIndegree, items);
            if (itemOrder.size() != items.size()) return {};
            
            result.insert(result.end(), itemOrder.begin(), itemOrder.end());
        }
        
        return result;
    }
    
private:
    vector<int> topologicalSort(vector<vector<int>>& graph, vector<int>& indegree) {
        queue<int> q;
        for (int i = 0; i < indegree.size(); i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> result;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            result.push_back(node);
            
            for (int next : graph[node]) {
                if (--indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        return result;
    }
    
    vector<int> topologicalSort(vector<vector<int>>& graph, vector<int>& indegree, vector<int>& nodes) {
        queue<int> q;
        for (int node : nodes) {
            if (indegree[node] == 0) {
                q.push(node);
            }
        }
        
        vector<int> result;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            result.push_back(node);
            
            for (int next : graph[node]) {
                if (--indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        from collections import deque, defaultdict
        
        # 为没有组的项目分配新组号
        group_id = m
        for i in range(n):
            if group[i] == -1:
                group[i] = group_id
                group_id += 1
        
        # 构建组间和组内依赖图
        group_graph = defaultdict(list)
        group_indegree = defaultdict(int)
        item_graph = defaultdict(list)
        item_indegree = defaultdict(int)
        
        for i in range(n):
            for prev in beforeItems[i]:
                if group[prev] != group[i]:
                    # 不同组间的依赖
                    group_graph[group[prev]].append(group[i])
                    group_indegree[group[i]] += 1
                else:
                    # 同组内的依赖
                    item_graph[prev].append(i)
                    item_indegree[i] += 1
        
        def topological_sort(graph, indegree, nodes=None):
            if nodes is None:
                nodes = list(range(group_id))
            
            queue = deque()
            for node in nodes:
                if indegree[node] == 0:
                    queue.append(node)
            
            result = []
            while queue:
                node = queue.popleft()
                result.append(node)
                
                for neighbor in graph[node]:
                    indegree[neighbor] -= 1
                    if indegree[neighbor] == 0:
                        queue.append(neighbor)
            
            return result
        
        # 对组进行拓扑排序
        group_order = topological_sort(group_graph, group_indegree, list(range(group_id)))
        if len(group_order) != group_id:
            return []
        
        # 按组分类项目
        group_to_items = defaultdict(list)
        for i in range(n):
            group_to_items[group[i]].append(i)
        
        result = []
        for g in group_order:
            items = group_to_items[g]
            if not items:
                continue
            
            # 对该组内的项目进行拓扑排序
            item_order = topological_sort(item_graph, item_indegree, items)
            if len(item_order) != len(items):
                return []
            
            result.extend(item_order)
        
        return result

public class Solution {
    public int[] SortItems(int n, int m, int[] group, IList<IList<int>> beforeItems) {
        // 为没有组的项目分配新组号
        int groupId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = groupId++;
            }
        }
        
        // 构建组间和组内依赖图
        var groupGraph = new List<int>[groupId];
        var groupIndegree = new int[groupId];
        var itemGraph = new List<int>[n];
        var itemIndegree = new int[n];
        
        for (int i = 0; i < groupId; i++) {
            groupGraph[i] = new List<int>();
        }
        for (int i = 0; i < n; i++) {
            itemGraph[i] = new List<int>();
        }
        
        for (int i = 0; i < n; i++) {
            foreach (int prev in beforeItems[i]) {
                if (group[prev] != group[i]) {
                    // 不同组间的依赖
                    groupGraph[group[prev]].Add(group[i]);
                    groupIndegree[group[i]]++;
                } else {
                    // 同组内的依赖
                    itemGraph[prev].Add(i);
                    itemIndegree[i]++;
                }
            }
        }
        
        // 对组进行拓扑排序
        var groupOrder = TopologicalSort(groupGraph, groupIndegree);
        if (groupOrder.Count != groupId) return new int[0];
        
        // 按组分类项目
        var groupToItems = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            if (!groupToItems.ContainsKey(group[i])) {
                groupToItems[group[i]] = new List<int>();
            }
            groupToItems[group[i]].Add(i);
        }
        
        var result = new List<int>();
        foreach (int g in groupOrder) {
            if (!groupToItems.ContainsKey(g)) continue;
            var items = groupToItems[g];
            
            // 对该组内的项目进行拓扑排序
            var itemOrder = TopologicalSort(itemGraph, itemIndegree, items);
            if (itemOrder.Count != items.Count) return new int[0];
            
            result.AddRange(itemOrder);
        }
        
        return result.ToArray();
    }
    
    private List<int> TopologicalSort(List<int>[] graph, int[] indegree, List<int> nodes = null) {
        var queue = new Queue<int>();
        
        if (nodes == null) {
            for (int i = 0; i < indegree.Length; i++) {
                if (indegree[i] == 0) {
                    queue.Enqueue(i);
                }
            }
        } else {
            foreach (int node in nodes) {
                if (indegree[node] == 0) {
                    queue.Enqueue(node);
                }
            }
        }
        
        var result = new List<int>();
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            result.Add(node);
            
            foreach (int next in graph[node]) {
                if (--indegree[next] == 0) {
                    queue.Enqueue(next);
                }
            }
        }
        
        return result;
    }
}

var sortItems = function(n, m, group, beforeItems) {
    // 为没有组的项目分配新组号
    let groupId = m;
    for (let i = 0; i < n; i++) {
        if (group[i]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析