『算法-ACM竞赛-图论』拓扑排序-模板

『算法-ACM 竞赛-图论』拓扑排序-模板

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
//字典序号最小
#include <cstdio>
#include <cstring>
#define MAXN 517
int G[MAXN][MAXN]; //路径
int in_degree[MAXN]; //入度
int ans[MAXN];
int n, m, x, y;
int i, j;

bool toposort()
{
for (i = 1; i <= n; i++) //从最小的开始寻找，
{ //这样保证了有多个答案时序号小的先输出
int k = 1;
while (in_degree[k] != 0&&k<=n) //寻找入度为零的点
k++;
if(k==n+1) return 0;
ans[i] = k;
in_degree[k] = -1;
//更新为-1，后边检测不受影响，相当于删除节点
for (int j = 1; j <= n; j++)
{
if (G[k][j])
in_degree[j]--; //相关联的入度减 1
}
}
return 1;
}

void init()
{
memset(in_degree, 0, sizeof(in_degree));
memset(ans, 0, sizeof(ans));
memset(G, 0, sizeof(G));
}

int main()
{
while (~scanf("%d%d", &n, &m))
{
init();
for (i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
if(G[x][y]==0) in_degree[y]++;
G[x][y] = 1;

        }
        toposort();
        for (i = 1; i < n; i++)
            printf("%d ", ans[i]);
        printf("%d\n", ans[n]);
    }
    return 0;

}

````
```cpp
//字典序最小2
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=500+10;
int n,m;
vector<int> G[maxn];
int in[maxn];
void topo()
{
    priority_queue<int,vector<int>,greater<int> > Q; //保证小值int先出队列
    int ans[maxn],cnt=0;
    for(int i=1;i<=n;i++)if(in[i]==0) Q.push(i);
    while(!Q.empty())
    {
        int u=Q.top(); Q.pop();
        ans[cnt++]=u;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(--in[v]==0)
                Q.push(v);
        }
    }
    printf("%d",ans[0]);
    for(int i=1;i<n;i++)
        printf(" %d",ans[i]);
    puts("");
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            in[v]++;
        }
        topo();
    }
    return 0;
}

````

```cpp
//一般的拓扑排序
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=500+10;
int n,m;
vector<int> G[maxn];
int in[maxn];
void topo()
{
    priority_queue<int,vector<int>,greater<int> > Q; //保证小值int先出队列
    int ans[maxn],cnt=0;
    for(int i=1;i<=n;i++)if(in[i]==0) Q.push(i);
    while(!Q.empty())
    {
        int u=Q.top(); Q.pop();
        ans[cnt++]=u;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(--in[v]==0)
                Q.push(v);
        }
    }
    printf("%d",ans[0]);
    for(int i=1;i<n;i++)
        printf(" %d",ans[i]);
    puts("");
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            in[v]++;
        }
        topo();
    }
    return 0;
}
算法 > ACM竞赛 > 图论
『算法-ACM竞赛-图论』拓扑排序-模板
https://chiamzhang.github.io/2024/06/29/『算法-ACM竞赛-图论』拓扑排序-模板/
Author
Chiam
Posted on
June 29, 2024
Licensed under