leetcode 周赛155 | 项目管理之拓扑排序算法
leetcode 周赛155 | 项目管理之拓扑排序算法
今天看了下leetcode周赛的题目，没怎么做，第四题是一道Hard题目，看了下题意感觉要用拓扑排序，但是这道题除了依赖关系，还有一个分组的变量，导致这道题处理起来会复杂些，可能需要2次拓扑排序或者1次复杂的拓扑排序。
下午看了下排名第一的题解，果然是2次拓扑排序，代码比较精简，值得学习一下。
来看下本次比赛这道题的通过次数
，这次是真的很低。
来看题：
5200. 项目管理 显示英文描述
公司共有 n 个项目和 m 个小组，每个项目要不没有归属，要不就由其中的一个小组负责。
我们用 group[i] 代表第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）
请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
同一小组的项目，排序后在列表中彼此相邻。 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 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、首先对于所有的项目，将他们之间的依赖关系连成边，然后进行拓扑排序，解决掉同一个组内元素先后的问题。
2、排序后，进行分组，按组的依赖关系连成边，然后进行拓扑排序，解决掉多个组的先后问题。
3、这时候可以将排序后的组合并起来，返回即可。
源代码：
const int MAXN = 30010;
vector<int> v[MAXN];
int deg[MAXN];
void clear(int n)
{
for (int i = 0; i < n; ++i)
{
v[i].clear();
deg[i] = 0;
}
}
void addedge(int x, int y)
{
v[x].push_back(y);
deg[y] ++;
}
int head, tail, Q[MAXN];
bool topsort(int n)
{
head = 1;
tail = 0;
for (int i = 0; i < n; ++i)
if (!deg[i])
{
Q[++tail] = i;
}
while (head <= tail)
{
int x = Q[head++];
for (auto y : v[x])
if (!--deg[y]) Q[++tail] = y;
}
return tail == n;
}
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
clear(n);
for (int i = 0; i < n; ++i)
{
for (auto x : beforeItems[i])
{
//元素间的依赖关系
addedge(x, i);
}
}
//top排序进行分组
if (!topsort(n)) return {};
int tmp_m = m;
for (int i = 0; i < n; ++i)
{
if (group[i] == -1)
{
group[i] = m++;
}
}
vector<vector<int>> v(m);
for (int i = 1; i <= n; ++i)
v[group[Q[i]]].push_back(Q[i]);
clear(m);
for (int i = 0; i < n; ++i)
{
for (auto x : beforeItems[i])
{
if (group[x] == group[i]) continue;
//组之间的依赖关系
addedge(group[x], group[i]);
}
}
//对组进行top排序
if (!topsort(m)) return {};
vector<int> ret;
//分组输出
for (int i = 1; i <= m; ++i)
{
for (auto x : v[Q[i]]) ret.push_back(x);
}
return ret;
}
};
再来回顾一下拓扑排序：
一个简单的问题
有n个任务，用1-n进行表示，任务可能存在依赖关系，(u,v)表示v需要依赖任务u，输出完成所有任务的序列。
拓扑排序
拓扑排序就是解决这种存在先后关系的问题的算法。在上面的问题中，可以把每个任务看成图上的一个节点，对于(u, v)表示 u→v。
比如有3个任务，表示为1，2，3，任务依赖关系为(2,3) (3,1) 那么就有如下图所示：
任务序列也就是2，3，1。对于有些图，序列可能是多个。
在图论中，由一个有向无环图DAG的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序
1 每个顶点出现且只出现一次； 2 若A在序列中排在B的前面，则在图中不存在从B到A的路径。
卡恩算法
卡恩于1962年提出的算法。简单来说就是，假设L是存放结果的列表，先找到那些入度为零的节点，把这些节点放到L中，因为这些节点没有任何的父节点。然后把与这些节点相连的边从图中去掉，再寻找图中的入度为零的节点。对于新找到的这些入度为零的节点来说，他们的父节点已经都在L中了，所以也可以放入L。重复上述操作，直到找不到入度为零的节点。如果此时L中的元素个数和节点总数相同，说明排序完成；如果L中的元素个数和节点总数不同，说明原图中存在环，无法进行拓扑排序。
伪代码
bool toposort() {
q = new queue();
for (i = 0; i < n; i++)
if (in_deg[i] == 0) q.push(i);
ans = new vector();
while (!q.empty()) {
u = q.pop();
ans.push_back(u);
for each edge(u, v) {
if (--in_deg[v] == 0) q.push(v);
}
}
if (ans.size() == n) {
for (i = 0; i < n; i++)
std::cout << ans[i] << std::endl;
return true;
} else {
return false;
}
}
简单的理解，遍历每个节点N，从N开始进行DFS搜索，如果能够完成搜索，则说明存在拓扑排序。如下代码。
// dfs 版本
bool dfs(int u) {
c[u] = -1;
for (int v = 0; v <= n; v++)
if (G[u][v]) {
if (c[v] < 0)
return false;
else if (!c[v])
dfs(v);
}
c[u] = 1;
topo.push_back(u);
return true;
}
bool toposort() {
topo.clear();
memset(c, 0, sizeof(c));
for (int u = 0; u <= n; u++)
if (!c[u])
if (!dfs(u)) return false;
reverse(topo.begin(), topo.end());
return true;
}