题目描述
公司共有 n
个项目和 m
个小组,每个项目要不没有归属,要不就由其中的一个小组负责。
我们用 group[i]
代表第 i
个项目所属的小组,如果这个项目目前无人接手,那么 group[i]
就等于 -1
。(项目和小组都是从零开始编号的)
请你帮忙按要求安排这些项目的进度,并返回排序后的项目列表:
- 同一小组的项目,排序后在列表中彼此相邻。
- 项目之间存在一定的依赖关系,我们用一个列表
beforeItems
来表示,其中beforeItems[i]
表示在进行第i
个项目前(位于第i
个项目左侧)应该完成的所有项目。
如果存在多个解决方案,只需要返回其中任意一个即可。
如果没有合适的解决方案,就请返回一个 空列表。
样例
输入:
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]
输入:
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]
不包含重复元素。
算法
(拓扑排序) $O(n + m + tot)$
- 首先将属于同一组的项目缩在一起(不考虑他们之间的依赖关系),组和组之间,以及组和不属于任何组的项目之间建立依赖关系,进行拓扑排序。
- 然后,在每个组内部建立依赖关系,分别进行拓扑排序,判断输出。
时间复杂度
- 多次拓扑排序,每个项目和组遍历常数次,故时间复杂度为 $O(n + m + tot)$,其中 $tot$ 为总边数。
空间复杂度
- 需要额外的空间建图和进行拓扑排序,故空间复杂度为 $O(n + m + tot)$。
C++ 代码
class Solution {
public:
vector<int> top_sort(queue<int>& q, const vector<vector<int>>& graph, vector<int>& indeg) {
vector<int> sorted;
while (!q.empty()) {
int sta = q.front();
sorted.push_back(q.front());
q.pop();
for (int i = 0; i < graph[sta].size(); i++) {
indeg[graph[sta][i]]--;
if (indeg[graph[sta][i]] == 0) {
q.push(graph[sta][i]);
}
}
}
return sorted;
}
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
vector<vector<int>> g(n + m);
// 外部拓扑排序前建立依赖关系时,组的编号范围为 [n, n + m - 1]。
vector<vector<int>> graph_outer(n + m), graph_inner(n);
vector<int> indeg_outer(n + m, 0), indeg_inner(n, 0);
for (int i = 0; i < n; i++)
if (group[i] != -1)
g[group[i] + n].push_back(i);
// 建立两种图的依赖关系。
for (int i = 0; i < n; i++)
for (int x : beforeItems[i])
if (group[x] == -1) {
if (group[i] == -1)
graph_outer[x].push_back(i);
else
graph_outer[x].push_back(group[i] + n);
} else {
if (group[i] == -1)
graph_outer[group[x] + n].push_back(i);
else {
if (group[x] != group[i])
graph_outer[group[x] + n].push_back(group[i] + n);
else {
graph_inner[x].push_back(i);
}
}
}
// 统计外部依赖关系每个点的入度
for (int i = 0; i < n + m; i++)
for (int j = 0; j < graph_outer[i].size(); j++)
indeg_outer[graph_outer[i][j]]++;
// 统计内部依赖关系每个点的入度
for (int i = 0; i < n; i++)
for (int j = 0; j < graph_inner[i].size(); j++)
indeg_inner[graph_inner[i][j]]++;
// 初始化外部拓扑排序队列
queue<int> q;
for (int i = 0; i < n + m; i++)
if (indeg_outer[i] == 0)
q.push(i);
vector<int> sorted_outer = top_sort(q, graph_outer, indeg_outer);
if (sorted_outer.size() != n + m)
return {};
vector<int> ans;
for (int v: sorted_outer) {
if (v < n) {
if (group[v] == -1) {
// 如果这个点是项目且不属于任何组
ans.push_back(v);
}
} else {
// 如果当前点是一个组
int cnt = 0;
for (int j: g[v]) {
// 找出组内所有项目,初始化内部拓扑排序队列
cnt++;
if (indeg_inner[j] == 0)
q.push(j);
}
vector<int> sorted_inner = top_sort(q, graph_inner, indeg_inner);
if (sorted_inner.size() != cnt)
return {};
ans.insert(ans.end(), sorted_inner.begin(), sorted_inner.end());
}
}
return ans;
}
};
太强了