为什么记录呢
因为不记录全忘了
虽然记了也不一定会看文章来源地址https://www.toymoban.com/news/detail-682212.html
- 有向无环图一定有拓扑序列
- 邮箱无环图 - 拓扑图
- 入度为0的点作为起点
- 入度为0的点入队列
- 枚举出边 t->j
- 删掉当前边，t->j . j的入度减1
- 判断j的入度是否为0，来判断是否加入队列
- 有环： 不存在入度为0的点
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 100010;
int h[maxn], e[maxn], ne[maxn], idx;
int q[maxn],d[maxn];
int n;
int hh = 0, tt = -1;
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topsort(){
while(hh <= tt){
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
d[j]--;
if(d[j] == 0){
q[++tt] = j;
// cout<<"j: "<< j << " ";
}
}
}
// cout<<"tt " << tt << "n-1 "<< n-1 << '\n';
return tt == n-1;
}
int main(){
int m,a,b;
memset(h , -1, sizeof h);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin>>a>>b;
add(a,b);
// cout<<"b "<< b << " ";
d[b]++;
}
for(int i = 1; i <= n; i++){
if(d[i] == 0){
// cout<<"i: " << i<<'\n';
q[++tt] = i;
}
}
if(topsort()){
for(int i = 0; i < n; i++){
cout<<q[i] << " ";
}
}else cout<<-1<< '\n';
return 0;
}
文章来源：https://www.toymoban.com/news/detail-682212.html
到了这里，关于搜索与图论-拓扑序列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
