给定一个n个点m条边的有向图，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入格式
第一行包含两个整数n和m
接下来m行，每行包含两个整数x和y，表示点x和点y之间存在一条有向边(x, y)。
输出格式
共一行，如果存在拓扑序列，则输出拓扑序列。
否则输出-1。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3算法：bfs
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=
100010;
int n, m, idx;
queue<
int>
q,p;
int h[N],e[N],ne[N],d[N];
vector<
int>
res;
void add(
int a,
int b){
e[idx]=
b;
ne[idx]=
h[a];
h[a]=idx++
;
}
bool top_sort(){
for(
int i=
1;i<=n;i++
)
if(!
d[i])q.push(i);
while(q.size()){
int t=
q.front();
res.push_back(t);
q.pop();
for(
int i=h[t];~i;i=
ne[i]){
int j=
e[i];
if(--d[j]==
0){
q.push(j);
}
}
}
return res.size()==
n;
}
int main(
void){
cin>>n>>
m;
memset(h,-
1,
sizeof(h));
for(
int i=
0,a,b;i<m;i++
){
cin>>a>>
b;
add(a,b);
d[b]++
;
}
if(top_sort()){
for(
int i=
0;i<n;i++)cout<<res[i]<<
' ';
}
else
cout<<
"-1"<<
endl;
return 0;
}
转载于:https://www.cnblogs.com/programyang/p/11185673.html
