(拓扑排序)给出一张 $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. 上述程序 (1) 中应该填写( )
2. 上述程序 (2) 中应该填写( )
3. 上述程序 (3) 中应该填写( )
4. 上述程序 (4) 中应该填写( )
5. 上述程序 (5) 中应该填写( )
陈伦制作 版权所无 粤ICP备16127491号-1