leetcode 周赛 round 155 5200. 项目管理 拓扑排序

缘起

瞄了一眼leetcode 周赛 round 155 的题目. 这题是困难级别. leetcode 周赛 round 155 5200. 项目管理

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
5200. 项目管理 显示英文描述 
用户通过次数12
用户尝试次数27
通过次数12
提交次数45
题目难度Hard
公司共有 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 <= 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]

说是困难其实没很难, 睡觉前在床上躺着想了一会儿就知道思路了. 两遍拓扑排序即可. 第一遍是项目之间的拓扑排序, 为了防止项目之间存在非DAG情形. 第二遍是项目组之间的拓扑排序. 是为了防止最终没有答案(因为要求相同项目组的项目要排在相邻位置，所以可以将若干项目缩点为项目组, 所以就是将项目组视作有向图的点进行拓扑排序即可).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class Solution {
public:
	vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
		first = true;
		int code = m; // 对于没有隶属于任何项目组的项目, 他们单独属于一个虚拟的项目组(而不能统一的属于-1,这太笼统了)
		for (int i = 0;i<group.size(); i++)
		{
			if (!~group[i]) // 如果项目i未归属于任何项目组
			{
				group[i] = code; // 项目i归属于一个虚拟的项目组code
				code++;
			}
		} // O(n) 预处理group数组
		vector<int> ans;
		memset(indeg, 0, sizeof(indeg));
		for (int i = 0; i<n;i++)
		{
			g[i].clear();
		}
		for (int i = 0; i<n; i++)
		{
			for (int j = 0; j<beforeItems[i].size(); j++) // 项目beforeItems[i][j] 必须在项目i前面完成, 即有弧 beforeItems[i][j]->i
			{
				indeg[i]++;
				g[beforeItems[i][j]].push_back(i); // 弧  beforeItems[i][j]->i
			}
		}
		if (!topsort(n, group)) 
		{
			return ans; // 拓扑无序, 返回空列表
		}
		first = false; // 第二次拓扑排序
		for (int i = 0; i<code;i++) // 重新建图对项目组进行拓扑排序, 注意, 算上虚拟的项目组,一共code个项目组
		{
			g[i].clear();
		}
		memset(indeg, 0, sizeof(indeg));
		for (int i = 0; i<n; i++)
		{
			for (int j = 0; j<beforeItems[i].size(); j++)
			{
				if (group[beforeItems[i][j]]==group[i]) // 同一个缩点的就不必了
				{
					continue;
				}
				indeg[group[i]]++;
				g[group[beforeItems[i][j]]].push_back(group[i]); // 项目组到项目组的弧(上面拓扑排序建的图是项目到项目的弧)
			}
		}
		if (!topsort(code, group)) // 如果项目组之间拓扑无序的话
		{
			return ans;
		}
		for (int i = 0; i<cnt; i++) // 开始拼装答案
		{
			for (int j = 0; j<belong[anss[i]].size(); j++)
			{
				ans.push_back(belong[anss[i]][j]);
			}
		}
		return ans;
	}

private:
	const static int maxn = 30005;
	int indeg[maxn], anss[maxn], cnt; //  cnt是anss中的元素, anss是拓扑排序的结果
	bool first; // true 表示是第一次拓扑排序, false表示第二次
	vector<int> g[maxn];
	vector<int> belong[maxn]; // belong[i]中装的都是属于项目组i的项目编号
	bool topsort(int n, vector<int> group) // 拓扑排序, 返回true表示拓扑有序
	{
		stack<int> s;
		cnt = 0;
		int nn = n;
		for (int i = 0; i<nn;i++)
		{
			if (!indeg[i])
			{
				s.push(i);
				n--;
				if (first) // 第一次拓扑排序
				{
					belong[group[i]].push_back(i); // 则belong[i]记录了第i组中依照拓扑序的项目
				}
				else // 第二次拓扑排序
				{
					anss[cnt++] = i;
				}
			}
		} // 初始化栈
		while(!s.empty())
		{
			int top = s.top();
			s.pop();
			for (int i = 0; i<g[top].size(); i++)
			{
				if (!--indeg[g[top][i]])
				{
					s.push(g[top][i]);
					n--;
					if (first)
					{
						belong[group[g[top][i]]].push_back(g[top][i]);
					}
					else
					{
						anss[cnt++] = g[top][i];
					}
				}
			}
		}
		return !n;
	}
};

ac情况

13 / 13 个通过测试用例 状态：通过
执行用时：168 ms 提交时间：1 分钟之前

ps: 真心不喜欢leetcode的代码风格~ 工业类型的代码.