AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
sca
,
2023-12-13 17:15:50
,
所有人可见
,
阅读 41
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
const int M = 2 * N;
int idx, n, m;
int sum = 1; //下标从1开始
int e[N], ne[M], h[N], d[N], ans[N];
queue <int> q;
void add (int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topsort()
{
//把入度为0的点先入队
for (int i = 1; i <= n; i++)
{
if (d[i] == 0) q.push(i); //因为是把i入队,题目里点的编号从1开始,所以下标要从1开始。否则结果就输出0 1 2了
}
//开始套BFS的模板
while (!q.empty())
{
int t = q.front();
ans[sum++] = t; //用ans[]存队头,用于最后输出拓扑序列
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j]--; //“删除边t→j”,然后j的入度-1
if (d[j] == 0) q.push(j); //如果j的入度变为0,则将其入队
}
}
return sum - 1 == n; //因为sum从1开始,如果该图有拓扑序列则最后必然有sum-1==n,可以输出sum看一下就知道了
}
int main ()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--)
{
int x, y;
cin >> x >> y;
add(x, y);
d[y]++; //y的入度+1
}
if (topsort())
{
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
else cout << -1;
}