AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
Hot_River
,
2021-05-10 10:12:39
,
所有人可见
,
阅读 205
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 100010, M = 2 * N;
int n, m, idx, head = 0, rear = -1;
int hh[N], e[M], ne[M], in[N], q[N]; //in[]保存每个结点的入度,q[]为模拟队列用来存储拓扑序列
//建立邻接表
void add(int a, int b)
{
e[idx] = b, ne[idx] = hh[a], hh[a] = idx ++ ;
in[b] ++ ;
}
//拓扑排序
bool topsort()
{
for (int i = 1; i <= n; i ++ )
if (in[i] == 0) q[ ++ rear] = i; //入度为0的结点入队
while (head <= rear)
{
int t = q[head ++ ];
for (int i = hh[t]; i != -1; i = ne[i])
{
int j = e[i];
if (--in[j] == 0) q[ ++ rear] = j; //子结点入度-1判断是否为0,为0则入队
}
}
return rear == n - 1; //如果n个结点全部入队则说明存在拓扑序列,否则不存在
}
int main()
{
cin >> n >> m;
memset(hh, -1, sizeof hh);
for (int i = 0; i < m; i ++ )
{
int a, b;
cin >> a >> b;
add(a, b);
}
if (topsort()){
//按照队列先进先出输出拓扑序列
for (int i = 0; i <= rear; i ++ )
cout << q[i] << " ";
}
else cout << -1;
return 0;
}