题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。
若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。
输入格式
第一行包含两个整数n和m
接下来m行,每行包含两个整数x和y,表示点x和点y之间存在一条有向边(x, y)。
输出格式
共一行,如果存在拓扑序列,则输出拓扑序列。
否则输出-1。
数据范围
1≤n,m≤105
样例
输入样例:
3 3
1 2
2 3
1 3
输出样例:
1 2 3
算法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(100010, vector<int>()); //入度记录
vector<int> invec(100010, 0);; //出度记录
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int start; int end;
cin >> start >> end;
invec[end]++;
outvec[start].push_back(end);
}
queue<int> q;
for (int i = 1; i <= n; i++) {
//找到第一个入度为0的点
if (invec[i] == 0) {
q.push(i);
}
}
vector<int> ret;
while (!q.empty()) {
int idx = q.front();
q.pop();
ret.push_back(idx);
//抹掉这个点的所有出度边 与入度计数
for (auto& e : outvec[idx]) {
if (e != -1) {
invec[e]--; //该点入度减1
if (invec[e] == 0) {
q.push(e);
}
e = -1; //抹掉该边
}
}
}
if(ret.size() == n)
for (auto& e : ret) {
cout << e << " ";
}
else
cout << -1;
return 0;
}
佬 为什么我加了个判断去除重边和自环就无法通过呢
改为
就可以了 求教
如果把拓扑序列 理解为选修课表, 自环就等于要学习高数你必须先学完高数,这个是不成立的。 视为失败情况。 你去除了自环就等于承认这种情况可以成功。
重边倒是没啥影响,未验证,个人理解。
懂了 谢谢佬
if (invec[e] == 0) {
q.push(e);
}
为什么入度为0才入队
根据拓扑的定义,如果一个点入度为0 ,那么他就没有前继节点。比起有前继节点的其他点,他的排位应该在前,先push 进ret中
大佬,如果是要输出所有的拓扑序列,该怎么写啊
能确定的先后次序的 那么就只有一种次序 没啥变化
如果是在序列里没有明确的先后次序,那就是一个简单的DFS输出排列组合了
见acwing 92~94
果然是我菜鸡目前掌握不了的内容
不不,可能是我没讲清楚。
类似这种拓扑序列
1 2 3 4 5.x 5.y 5.z 6 7 8 9
那么已经确认次序的 1234 6789 就没变化
只需要dfs将 5.x 5.y 5.z的排列组合 写出来就好了
答案如下
1234 5.x 5.y 5.z 6789
1234 5.y 5.x 5.z 6789
1234 5.y 5.z 5.x 6789
剩下的排列组合。
类似这种
应该是将所有入度为0的点入队吧
是的 ,应该是所有入度为0的点入队, 已经修正。谢谢!
大佬,你的代码这个样例过不去呀