共42道题,当前是第18

初赛真题

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

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

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

#include<algorithm>
#include<cstdio>
#include<vector>
#define N 200020
using namespace std;

int n, m;
vector < int > G[N];
int q[N], hd, tl;
int du[N];
int ans[N], tot;

void topo() {
	hd = 1, tl = 0;
	for (int i = 1; i <= n; i++)
		if (_____(1)_____) q[++tl] = i;
	while (hd <= tl) {
		int u = q[hd++];
		ans[++tot] = u;
		for (int i = 0; _____(2)_____; i++) {
			int v = G[u][i];
			du[v]--;
			if (!du[v]) _____(3)_____;
		}
	}
	if (tot != n) puts("-1");
	else {
		for (int i = 1; i <= n; i++)
			printf("%d ", ans[i]);
	}
}

int main() {
	scanf("%d%d", & n, & m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", & x, & y);
		_____(4)_____;
		_____(5)_____;
	}
	topo();
	return 0;
}

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