跳转链接
https://www.acwing.com/problem/content/850/ 来源：模板题
题目描述
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。 若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式 第一行包含两个整数 n 和 m。 接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。 输出格式 共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。 否则输出 −1。 数据范围 1 , 10^5^
输入样例
3 3 1 2 2 3 1 3 输出样例 1 2 3
题解思路
参考https://www.acwing.com/solution/content/21908/TIPS: 1. 拓扑排序基于BFS实现 2. 拓扑排序的答案不唯一 3. 一个图只要有环，一定不是拓扑序列 4. 每个有向无环图都至少存在一个入度为0的点
代码
cpp
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m, a, b, idx, cnt;
int e[N], ne[N], h[N], d[N], top[N]; //d表示点的入度, top用来存储序列
void add(int a, int b)
{
e[idx] = b,ne[idx] = h[a], h[a] = idx++;
}
bool top_sort()
{
queue<int>q;
for (int i = 1; i <= n; i++)
if (d[i] == 0) q.push(i); // 将入度为零的点入队
while (q.size())
{
int t = q.front();
top[cnt++] = t;
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j]--; // 删除点t指向点j的边
if(d[j] == 0) q.push(j); // 如果点j的入度为零了,就将点j入队
}
}
if(cnt == n) return true; // 计数等于n时，表示全部都已排序，可以构成拓扑序列
else return false;
}
int main()
{
memset(h, -1, sizeof h); // 如果程序时间溢出，就是没有加上这一句
cin >> n >> m;
while (m--)
{
cin >> a >> b;
add(a, b); // 因为是a指向b,所以b点的入度要加1
d[b]++;
}
if(top_sort())
{
for (int i = 0; i < n; i++) cout << top[i] << ' ';
//经上方循环可以发现队列中的点的次序就是拓扑序列
//注:拓扑序列的答案并不唯一,可以从解析中找到解释
}
else cout << -1;
return 0;
}
