AcWing 848. 有向图的拓扑序列-细节注释
原题链接
简单
作者:
现代修士o_O
,
2021-04-28 11:04:43
,
所有人可见
,
阅读 146
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
//邻接表四件套,记得memset初始化h
//h[i] 下标为i的结点的下一个结点
//e[i] 下标为i的结点的图中的编号
//ne[i] 下标为i的结点的下一个结点的下标
//idx 管理下标,不重复,指向最后一个可以的下标
int h[N], e[N], ne[N], idx;
//bfs两件套
//d[i] 编号为i的结点的入度
//q[N] 队列
int d[N], q[N];
void add(int a, int b)//头插
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )//如果是有向无环图,即拓扑图,则必有至少一个结点的入度为0
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j] --;
if (!d[j]) q[ ++ tt] = j;
}
}
// if (tt == n - 1) return true;
// else return false;
// 下面的这个相当于上面的这个if表达式
return tt == n - 1; // tt从-1到达了n-1,则代表有n个结点进入了队列,是个无环图!
}
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 ++ ) printf("%d ",q[i]);
puts("");
}
else puts("-1");
return 0;
}