拓扑排序
拓扑排序：在一个 DAG（有向无环图） 中，我们将图中的顶点（u，v）以线性方式进行排序，使得对于任何的顶点u到v的有向边（u，v）, 都可以有u在v的前面。
应用：可以判定一个图是否有环。
算法的实现过程：
先遍历所有的边，将所有入度为零的点加入到队列中。然后取出队头元素，对该元素连接的边进行扩展，如果该点的入度减1为0，就说明这个点一定在起点的后面，再次将该点入队，一直执行到队列为空为止。
模板:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
bool topsort(){
for(int i = 1; i <= n; i++){
if(d[i] == 0) q.push(i);
}
int cnt = 1;
while(q.size()){
int t = q.front();
top[cnt] = t;
q.pop();
cnt++;
for(int i = head[t]; ~i ; i = ne[i]){
int v = e[i];
if(--d[v] == 0) q.push(v);
}
}
if(cnt-1 == n) return true;
return false;
}
|
有向图的拓扑序列
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1−1。
数据范围
1≤n,m≤1e5
输入样例：
输出样例：
代码
个人
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
|
#include<bits/stdc++.h>
using namespace std;
const int N = 100100;
int e[N],ne[N],f[N],idx = 0;
int record[N];
void add(int a,int b) {
e[++idx] = b;
ne[idx] = f[a];
f[a] = idx;
}
int main() {
int n,m;cin>>n>>m;
queue<int>q;
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;add(a,b);
record[b] += 1;
}
for(int i=1;i<=n;i++){
if (record[i] == 0) {
q.push(i);
}
}
vector<int>res;
while(!q.empty()){
int top = q.front();
q.pop();
res.push_back(top);
for(int i=f[top];i!=0;i = ne[i]){
record[e[i]]--;
if (record[e[i]] == 0) {
q.push(e[i]);
}
}
}
if (res.size() == n) {
for(int i=0;i<n;i++){
printf("%d ",res[i]);
}
} else{
cout<<-1<<endl;
}
}
|
板子
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
66
67
68
69
| #include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
return tt == n - 1;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
d[b] ++ ;
}
if (!topsort()) puts("-1");
else
{
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
puts("");
}
return 0;
}
|
