①处填写什么?
(拓扑排序)给出一张n个节点m条边的有向图,求出该图的一个拓扑排序,若无拓扑排序输出-1。输入:
第一行两个正整数n,m表示点数与边数。接下来m行,每行两个正整数x,y表示节点x到节点y之间有一条有向边。输出:
一个拓扑序,按拓扑序输出点的编号。若拓扑序不唯一,输出任意一个均可。若无拓扑序,输出-1。
关于拓扑序的例子,如学校里有A,B,C,D四门课程,要求课程B,C必须在学习课程A之后
才能学习,课程D必须在学习课程B,C之后学习。则序列ABCD与序列ACBD均是合理的拓扑序,而序列ABDC与序列BACD等均不是拓扑序。即在安排某课程时,其前置课程必须全部学习完毕。试补全程序。
#include <algorithm>
#include <cstdio>
#include <vector>
#define N 200020
using namespace std;
vector<int> G[N];
int n, m;
#include <cstdio>
#include <vector>
#define N 200020
using namespace std;
vector<int> G[N];
int n, m;
vector<int> q[N], hd, tl;
int du[N];
#include <algorithm>
#include <cstdio>
#include <vector>
#define N 200020
using namespace std;
vector<int> G[N];
int n, m;
vector<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( (___①处__ ) q[++tl] = 1 )
while (hd <= tl ){
int u = q[hd++];
ans[++tot] = u;
for ( int i = 0; ___②处__ i <= n; i+++ )
{
int v = G[u][i];
du[v]--;
if(!=0) ____③处___ ;
}
}
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);
_____④处___ _;
____⑤处___;
}
topo();
}
du[i]
chx<=1
b[i]
q[i]