题意:
一共有 $n$ 个项目,$m$ 个小组。每个项目或许隶属于一个 $group$,或许不属于任何一个 $group$。$group[i]$ 表示第 $i$ 个项目所在的小组,$group[i]==-1$ 表示不属于任何一个小组。$before[i]$ 表示完成第 $i$ 个项目需要完成的前置项目,要求在这些条件下返回一个合法的项目执行顺序,每个小组内的项目在执行顺序上是连续的,不能分开。
数据范围:$1\leq m\leq n\leq 30000, 0 \leq group[i] < m, 0\leq before[i][j] < n$
题解:
这是一道很好的拓扑排序题,需要对拓扑排序需要有一定的理解。
首先进行小组之间的拓扑排序,然后对小组内进行拓扑排序。
小组之间的拓扑排序需要对每个项目 $i$ 遍历,对于 $before[i][j]$ 和 $i$ 不属于同一小组的,即存在严格的先后执行顺序,那么这两个小组也就存在了严格的先后执行顺序。
在小组之间的拓扑排序结束后,再对每个小组的项目进行拓扑排序,那么这里对于每个小组内的项目 $i$,当 $before[i][j]$ 和 $i$ 属于同一小组的,即存在严格的组内先后执行顺序。
当小组之间的拓扑排序不能得到一个完整的执行顺序序列或者任意一个小组内的拓扑排序不能得到组内的完整的执行顺序序列,则返回空列表,否则返回任意一个合法的执行顺序。
代码:
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& before) {
// 1. 先确定组与组的拓扑排序
// 1.1. 给每个项目都编组,没有组的单独成组
for (auto& c: group) if (c == -1) c = m++;
vector<int> d_group(m, 0);
vector<int> d_ingroup(n, 0);
vector<vector<int>> e_group(m, vector<int>());
vector<vector<int>> e_ingroup(n, vector<int>());
for (int i = 0; i < n; ++i) {
int gb = group[i];
for (auto v: before[i]) {
int ga = group[v];
if (ga != gb) {
d_group[gb] += 1;
e_group[ga].push_back(gb);
} else {
d_ingroup[i] += 1;
e_ingroup[v].push_back(i);
}
}
}
// 1.2 进行组之间的拓扑排序
vector<int> temp(m);
int hh = 0, tt = -1;
for (int i = 0; i < m; ++i)
if (d_group[i] == 0) temp[++tt] = i;
while (hh <= tt) {
int u = temp[hh++];
for (int v: e_group[u])
if (--d_group[v] == 0)
temp[++tt] = v;
}
// 1.3. 小组间拓扑排序失败
if (tt + 1 != m) {
return {};
}
// 2. 确定每个组内的拓扑排序
// 2.1. 处理得到每个组内的元素
vector<vector<int>> every_group(m, vector<int>());
for (int i = 0; i < n; ++i) every_group[group[i]].push_back(i);
vector<int> ans;
vector<int> res;
for (int i = 0; i < m; ++i) {
auto& u = every_group[temp[i]];
res.resize(u.size());
hh = 0, tt = -1;
// 2.2. 进行小组之间的拓扑排序
for (int i : u)
if (d_ingroup[i] == 0) res[++tt] = i;
while (hh <= tt) {
int t = res[hh++];
for (int v: e_ingroup[t])
if (--d_ingroup[v] == 0)
res[++tt] = v;
}
// 2.3. 小组间拓扑排序失败
if (tt + 1 != u.size()) {
return {};
}
ans.insert(ans.end(), res.begin(), res.end());
}
return ans;
}
};