【笔记】 拓扑排序

发表于

这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战.

对于任何有向图而言，其拓扑排序为其所有结点的一个线性排序（对于同一个有向图而言可能存在多个这样的结点排序）。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。

拓扑排序常见于判断有向图是否有环、统计dag的信息等。

算法

记录每个节点的入度，把入度为0的节点加入队列中。
每次从队列中取出一个点，把它相连的节点的入度都减一，表示删除了这个节点。
队列为空后，如果还有点没有被访问过，证明有环。
无环的情况下，节点出队顺序即是一个拓扑序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
cpp复制代码struct Node
{
	int indegree; //入度
	vector<int> edgs; //邻接表
}node[M];

/* 返回是否有环 */
bool topo_sort(int n)
{
	queue<int> q;
	for(int i=1; i<=n; ++i)
		if(node[i].indegree==0)
			q.push(i);
	int cnt = 0; //可被排序的节点
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		++cnt;
		for(int v:node[u].edgs)
			if(--node[v].indegree==0)
				q.push(v);
	}
	return cnt<n;
}

例题

1. hihoCoder #1174 : 拓扑排序·一

给一张有向图，判断是否有环。

模板题

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
cpp复制代码/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read();
const int M = 100016, MOD = 1000000007;
/*topological-sort*/

struct Node
{
	int indegree;
	vector<int> edgs;
}node[M];

/* 返回是否有环 */
bool topo_sort(int n)
{
	queue<int> q;
	for(int i=1; i<=n; ++i)
		if(node[i].indegree==0)
			q.push(i);
	int cnt = 0; //可被排序的节点
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		++cnt;
		for(int v:node[u].edgs)
			if(--node[v].indegree==0)
				q.push(v);
	}
	return cnt<n;
}

int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	int T = read();
	while(T--)
	{
		memset(node,0,sizeof(node));
		int n=read(), m=read();
		while(m--)
		{
			int a = read(), b = read();
			node[a].edgs.push_back(b);
			++node[b].indegree;
		}
		printf("%s\n",topo_sort(n)?"Wrong":"Correct");
	}

    return 0;
}


inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

2. hihocoder #1175 : 拓扑排序·二

给一张有向无环图，初始时给某些节点释放一个病毒。病毒会在本节点留下一个标本，然后复制给一个节点指向的所有子节点，并且从子节点再次重复这个过程。问整个过程结束后所有节点的病毒数量总和。

考虑拓扑排序，当一个节点没有入度时，就让它开始复制，统计完它上面的病毒数后删去这个节点即可。

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
cpp复制代码/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read();
const int M = 100016, MOD =  142857;

struct Node
{
	vector<int> edgs;
	int ind;
	int val;
}node[M];

int topo_sort(int n)
{
	queue<int> q;
	for(int i=1; i<=n; ++i)
	{
		if(node[i].ind==0)
			q.push(i);
	}
	int ans = 0;
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		ans = (ans + node[u].val) % MOD;
		for(int v:node[u].edgs)
		{
			node[v].val = (node[v].val + node[u].val) % MOD;
			if(--node[v].ind == 0)	q.push(v);
		}
	}
	return ans;
}
int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	memset(node, 0, sizeof(node));
	int n=read(), m=read(), k=read();
	for(int i=1; i<=k; ++i)
		++node[read()].val;
	for(int i=1; i<=m; ++i)
	{
		int a=read(),b=read();
		node[a].edgs.push_back(b);
		++node[b].ind;
	}
	int ans = topo_sort(n);
	printf("%d\n",ans );
    return 0;
}


inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

3. HDU 4857

现在有n个人需要排序，给定一些要求(i,j)(i,j)(i,j)，表示iii必须在jjj的前面。在满足这些条件的同时，需要让1号尽量往前，再让2号尽量往前，依次类推。数据保证有解。

注意这个顺序并非字典序最小，比如对于以下dag：
在这里插入图片描述
字典序最小的排序是：3 5 6 4 1 7 8 9 2
题目要求排序是： 6 4 1 3 9 2 5 7 8，因为要让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
cpp复制代码/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read();
const int M = 30016, MOD = 1000000007;

struct Node
{
	int ind;
	vector<int> edges;
}node[M];
vector<int> topo_sort(int n)
{
	priority_queue<int> pq;
	for(int i=1; i<=n; ++i)
	{
		if(node[i].ind==0)
			pq.push(i);
	}
	vector<int> res;
	while(!pq.empty())
	{
		int u=pq.top(); pq.pop();
		res.push_back(u);
		for(int v:node[u].edges)
		{
			if(--node[v].ind==0)
				pq.push(v);
		}
	}
	return res;
}
int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	int T = read();
	while(T--)
	{
		memset(node, 0, sizeof(node));
		int n=read(), m=read();
		while(m--)
		{
			int a=read(),b=read();
			node[b].edges.push_back(a);
			++node[a].ind;
		}
		vector<int> ord = topo_sort(n);
		reverse(ord.begin(), ord.end());
		for(int i=0;i<(int)ord.size();++i)
			printf("%d%c",ord[i]," \n"[i==(int)ord.size()-1] );
	}

    return 0;
}


inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

本文也发表于我的 csdn 博客中。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%