拓扑排序
定义：若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x,y)$，$x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的一个拓扑序列。
拓扑序列只存在于有向图中，可以证明，所有的有向无环图($DAG$)都一定有至少一个拓扑序列。
分析：若一个点的入度为零，则这个点可以排在最前面的位置，因此
- 将所有入度为零的点入队
- 取出队首$t$，枚举$t$的所有出边，删除这些边，若某条边$(t,v)$删除后$v$的入度为零，则将$v$入队，重复，直至队列为空。
- 若仍有未入队的点，则一定存在环。
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],ne[N],to[N];
int cnt;
int d[N];
void addedge(int u,int v){
ne[++cnt]=h[u];
h[u]=cnt;
to[cnt]=v;
d[v]++;
}
queue<int>ans;
int idx;
int n,m;
void topsort(){
queue<int>q;
for(int i=1;i<=n;i++){
if(d[i]==0){
q.push(i);
ans.push(i);
idx++;
}
}
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=h[t];i;i=ne[i]){
d[to[i]]--;
if(d[to[i]]==0){
q.push(to[i]);
ans.push(to[i]);
idx++;
}
}
}
if(idx==n){
while(!ans.empty()){
cout << ans.front() << ' ';
ans.pop();
}
}
else{
cout << -1;
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v;
cin >> u >> v;
addedge(u,v);
}
topsort();
return 0;
}
|