共42道题,当前是第42题
给出一张 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。
1. ___ (1) ___
2. ___ (2) ___
3. ___ (3) ___
4. ___ (4) ___
5. ___ (5) ___
陈伦制作 版权所无 粤ICP备16127491号-1