地址 https://www.acwing.com/problem/content/description/850/
题目描述
给定一个n个点m条边的有向图，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入格式
第一行包含两个整数n和m
接下来m行，每行包含两个整数x和y，表示点x和点y之间存在一条有向边(x, y)。
输出格式
共一行，如果存在拓扑序列，则输出拓扑序列。
否则输出-1。
数据范围
1≤n,m≤105
样例
输入样例： 输出样例：
算法1
拓扑排序流程为BFS 流程如下
1 首先找到第一个入度为0 的点 放入待处理队列，记录答案拓扑数组中 拓扑的必要条件
2 然后从该点连接的各个点 做以下操作：
2.1 删除该边后，查看从该点连接的的点的入度
2.2 如果入度为0 那么该点放入待处理队列，记录答案拓扑数组中， 再次进行BFS 直到待处理队列为空
C++ 代码
#include <iostream> #include <iostream>
#include <vector>
#include <queue> using namespace std; int n, m;
vector<vector<int>> outvec(, vector<int>()); //入度记录
vector<int> invec(, );; //出度记录 int main()
{
cin >> n >> m; for (int i = ; i < m; i++) {
int start; int end;
cin >> start >> end;
invec[end]++;
outvec[start].push_back(end);
}
queue<int> q;
for (int i = ; i <= n; i++) {
//找到第一个入度为0的点
if (invec[i] == ) {
q.push(i);
break;
}
} vector<int> ret;
while (!q.empty()) {
int idx = q.front();
q.pop(); ret.push_back(idx); //抹掉这个点的所有出度边 与入度计数
for (auto& e : outvec[idx]) {
if (e != -) {
invec[e]--; //该点入度减1 if (invec[e] == ) {
q.push(e);
}
e = -; //抹掉该边
}
}
} if(ret.size() == n)
for (auto& e : ret) {
cout << e << " ";
}
else
cout << -; return ;
} 作者：defddr
链接：https://www.acwing.com/solution/acwing/content/4196/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。