给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 -1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x, y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 -1。
数据范围
1 < n,m < 10^5
输入样例：
输出样例：
算法思想
首先，存在拓扑序列，必定是有向无环图，如果是有向有环图一定没有拓扑序列，无向图更别说了。
核心思想：
- n个节点，将入度为0的节点全部入队
- 删除掉所有入度为0的节点，在这个过程中，被删掉的节点不妨设为
t - 遍历
t节点的邻边节点，让t节点的所有邻边节点入度减1，如果邻边节点入度被减之后恰好为0，则入队
此题，n的数量达到了10^5。所以需要使用邻接表，当然邻接矩阵算法也写下来，用于借鉴。
时间复杂度分别为o(n + m)和o(n^2)。
需要注意的是：
邻接矩阵的重边造成的影响需要在加边的时候进行判断，维护入度，不让重边的出现导致入度混乱。
或者，在topsort的时候将重边一起删掉，也意味着重边入度也要减少
1
| while(g[t][j]) --g[t][j],--d[j];
|
使用邻接表就不需要加判断了，因为邻接表在加边的时候，重边不仅加进去了，在topsort的时候
它会处理重边，所以入度一直是正确的。代码实现1
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
70
71
72
73
| #include <iostream>
using namespace std;
const int N = 100010;
int n, m;
struct Node{
int id;
Node * next;
Node(int _id): id(_id), next(NULL){}
} * head[N];
int d[N], q[N], hh = 0, tt = -1;
void add(int a, int b){
Node * p = new Node(b);
p -> next = head[a];
head[a] = p;
}
int topsort(){
for(int i = 1; i <= n; i++)
if(!d[i])
q[++tt] = i;
while(hh <= tt){
int t = q[hh++];
for(Node * p = head[t]; p; p = p -> next){
if(--d[p -> id] == 0){
q[++tt] = p -> id;
}
}
}
return tt == n - 1;
}
int main(){
cin >> n >> m;
while(m --){
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
if(!topsort()) puts("-1");
else{
for(int i = 0; i < n; i++)
cout << q[i] << " ";
}
return 0;
}
|
代码实现2
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
| #include <iostream>
using namespace std;
const int N = 1010;
int g[N][N];
int d[N];
int q[N], tt = -1, hh = 0;
int n, m;
bool topsort() {
for (int i = 1; i <= n; i++) {
if (!d[i]) {
q[++tt] = i;
}
}
while (hh <= tt) {
int t = q[hh++];
for (int j = 1; j <= n; j++) {
if (g[t][j]) {
while(g[t][j]) --g[t][j],--d[j];
if (d[j] == 0) {
q[++tt] = j;
}
}
}
}
return tt == n - 1;
}
int main() {
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
g[a][b]++;
d[b]++;
}
if (!topsort()) {
puts("-1");
} else {
for (int i = 0; i < n ; i++) {
cout << q[i] << " ";
}
cout << endl;
}
return 0;
}
|
代码实现3
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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2, INF = 0X3F3F3F3F;
int h[N], e[M], ne[M], idx;
int d[N];
int q[N], hh = 0, tt = -1;
int n, m;
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topsort(){
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; i = ne[i]){
int j = e[i];
if(--d[j] == 0){
q[++tt] = j;
}
}
}
return tt == n - 1;
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
while(m --){
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
if(!topsort()) puts("-1");
else {
for(int i = 0; i < n; i++){
cout << q[i] << " ";
}
}
return 0;
}
|
