拓扑排序
[toc]
$\qquad$有向图才存在拓扑序列。
$\qquad$如果一个图是存在环的,那么这一个图就不存在拓扑序列(所以无向图不存在拓扑序列。)
$\qquad$所以有向无环图也被称为拓扑图。
mermaid graph LR; A==>B B==>C A===>C
$\qquad$对于上面的这一个图,他的拓扑序列为:
A B C
大事蔡!拓扑序列的定义
$\qquad$对于任意的一条边,要求拓扑序列中发出边的元素,一定在收到边的元素的前面。对于满足上述条件的序列就称为图的拓扑序列。
如何求一个图的拓扑序列
$\qquad$我们通过定义,可以发现:
- 所有入度为0的点,均可以放在拓扑序列的最前面
- 如果第一步中所有的点入度均不为0,那么这一个图就存在环,不存在拓扑序列
- 然后删除和这一个点连起来的所有的边。
- 如果图中已经没有没有访问过的点了,拓扑序列构造完毕。
- 重复执行第1~4步
啊这,上代码
邻接矩阵
#include <bits/stdc++.h>
using namespace std;
int n, m; // 全局变量
int in_deg[1000010] ; // in_deg[i] 代表 i 节点的入度为几。
int top_sequence[1000010]; // 拓扑序列的数组定义。
int mp[1010][1010]; // 邻接矩阵
bool vis[100010];
int main()
{
cin >> n; // n代表点的数目
cin >> m; // m代表边的数目
for (int i = 0; i < m; i ++)
{
int a, b;
scanf ("%d%d", &a, &b);
mp[a][b] = true; // 加边,注意是有向图
in_deg[b] ++; // 记录一下入度的数目
}
queue <int> q; // 广搜所需要的队列
for (int i = 1; i <= n; i ++)
if (in_deg[i] == 0)
q.push(i), vis[i] = true; // 入队,并且标记
int tot = 0; // 序列长度
while (! q.empty())
{
int f = q.front();
top_sequence[++ tot] = f;
q.pop();
for (int i = 1; i <= n; i ++)
if (mp[f][i] == true)
{
mp[f][i] = false; // 取消连边
in_deg[i] --;
}
for (int i = 1; i <= n; i ++)
if (! vis[i] && in_deg[i] == 0) // 判断是否标记,并且入度是否已经为0
vis[i] = true, q.push(i);
}
if (tot != n) // 有环,无向图
{
puts("-1");
return 0;
}
for (int i = 1; i <= n; i ++)
printf ("%d ", top_sequence[i]);
puts(""); // 换行
return 0;
}
邻接表
#include <bits/stdc++.h>
using namespace std;
int n, m;
int head[100010];
int to[100010];
int nxt[100010];
int E;
int d[100010];
int q[100010];
void add(int a, int b)
{
to[E] = b;
nxt[E] = head[a];
head[a] = E;
E ++;
}
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 = head[t]; ~i; i = nxt[i])
{
int &j = to[i];
d[j] --;
if(! d[j]) q[++ tt] = j;
}
}
return tt == n - 1;
}
int main()
{
cin >> n >> m;
memset(head, -1, sizeof head);
for(int i = 0; i < m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
d[b] ++;
}
if(topsort() == true)
{
for(int i = 0; i < n; i ++)
{
printf("%d ", q[i]);
}
puts("");
}
else
{
puts("-1");
}
return 0;
}
一种奇怪的代码(好多电脑不能运行,我的电脑能运行)
#define EOF -1
int main()
{
asm ("44 cp dd.it");
asm ("48 cp a.out");
asm ("swap 44 48");
asm ("goto 3 before [EOF]");
for (int i = 0; i < n; i ++)
{
asm (0x3f, 0x3c, 0x7f, 0x10, 0x20, "cpy 52");
asm (0x3f, 0x3c, 0x7f, 0x10, 0x20, "cpy 56");
asm ("goto 10 before [EOF]");
}
asm ("print", 0x3f : 0x7f);
asm ("printch", 0x20);
return 0;
}