AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
小牛马
,
2021-11-26 11:50:50
,
所有人可见
,
阅读 142
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];//q是队列,d表示每个数的入度
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int topsort()
{
int hh = 0, tt = -1;
for(int i = 1; i <= n; i ++)//必须从1开始,因为排序的数字是从1开始的
{
if(!d[i]) q[ ++ tt] = i;
}
while(hh <= tt)//剩下的都是入度不为0的
{
int t = q[hh ++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];//无需判断,入度为0的已经加入了, 剩下的都是入度不为0的
d[j] --;
if(!d[j])
q[ ++ tt] = j;
}
}
return tt == n - 1;//因为对头是从0开始的所以判断的时候要让队尾等于n-1
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a,b);
d[b] ++;
}
if(topsort())
{
for(int i = 0; i < n; i ++)//因为所有入度为0的数都加到队列里面,所有直接输出队列就ok
printf("%d ",q[i]);
}
else puts("-1");
return 0;
}