共42道题,当前是第42

Description

给出一张 n 节点 m 条边的有向图,求出该图的一个拓扑排序,若无拓扑排序输出 −1

输入:第一行两个正整数 n, m 表示点数和边数。接下来 m 行,每行三个正整数 x, y 表示节点 x > y 之间有一条边。

输出:一个拓扑序:按拓扑序输出点的编号。若拓扑序不唯一,输出任意一个均可。若无拓扑序,输出 −1。\

1	#include <algorithm>
2	#include <cstdio>
3	#include <vector>
4	#define N 200020
5	using namespace std;
6	int n, m;
7	vector <int> G[N];
8	int q[N], hd, tl;
9	int du[N];
10	int ans[N], tot;
11	void topo(){
12		hd = 1, tl = 0;
13		for (int i = 1; i <= n; ++i){
14			if (___ (1) ___) q[++tl] = i;
15		}
16		while (hd <= tl){
17			int u = q[hd++];
18			ans[++tot] = u;
19			for (int i = 0; ___ (2) ___; ++i){
20				int v = G[u][i];
21				du[v]--;
22				if (!du[v]) ___ (3) ___;
23			}
24		}
25		if (tot != n) puts("-1");
26		else {
27			for (int i = 1; i <= n; ++i)
28				printf("%d ", ans[i]);
29		}
30	}
31	int main(){
32		scanf("%d%d", &n, &m);
33		for (int i = 1; i <= m; ++i){
34			int x, y;
35			scanf("%d%d", &x, &y);
36			___ (4) ___;
37			___ (5) ___;
38		}
39		topo();
40		return 0;
41	}

1.    D。

2.    C。

3.    A。

4.    B。

5.    C。

这段代码实现了拓扑排序,而且跟上道题的代码风格相似,通过数组的方式维护了队列。拓扑排序中要注意的就是对节点入度 du的维护,只有入度为0的点才可以被加入到队列(拓扑序)中。对于入度的维护需要从一开始加边就开始维护,之后每次删点后也要判断涉及到的点的入度是否为 0

Question

1. ___ (1) ___

2. ___ (2) ___

3. ___ (3) ___

4. ___ (4) ___

5. ___ (5) ___

陈伦制作 版权所无 粤ICP备16127491号-1