Trace
acwing 848. 有向图的拓扑序列
传送门：https://www.acwing.com/problem/content/850/
Problem
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1。
数据范围
$1\leq n,m\leq 10^5$
输入样例：
输出样例：
思路
拓扑排序：记录每个节点入度，从入度为0的节点开始$bfs$。
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> e[N];
int d[N];
int n,m;
int ans[N];
int idx;
bool bfs(){
queue<int> q;
for(int i=1;i<=n;i++){
if(d[i]==0){
q.push(i);
ans[idx++]=i;
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
d[v]--;
if(d[v]==0){
ans[idx++]=v;
q.push(v);
}
}
}
for(int i=1;i<=n;i++){
if(d[i]!=0){
return false;
}
}
return true;
}
int main()
{
cin>>n>>m;
while(m--){
int x,y;
cin>>x>>y;
e[x].push_back(y);
d[y]++;
}
if(bfs()){
for(int i=0;i<n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
else{
cout<<"-1"<<endl;
}
return 0;
}
|
