拓扑排序

拓扑排序

前言

拓扑排序是一种图论算法，拓扑图被简称为 \(\text{DAG}\)（有向无环图）。

下面来说说拓扑序的定义吧：对于一个有向图 \(G\)，拓扑序是关于这个图的一个线性序列，这个序列满足当 \(<u,v> \in G\) 且 \(u \to v\) 时，\(u\) 在 \(v\) 的前面。这里解释的可能比较浅显，详情请查阅百度百科。

算法讲解

例题 AcWing 1191. 家谱树

一般的拓扑排序分为这几步：

1. 统计每个点的入度，入度为 \(0\) 的点入队；
2. 将队头拿出，遍历其所能到达的点 \(j\)，将 \(d_j - 1\)，如果 \(d_j = 0\)，入队；
3. 重复 2.，直到跑完整个图；

这是一个算是比较简单的算法了 此题是裸的 \(\text{topsort}\)，代码放在下面了。

AC Code of AcWing 1191. 家谱树

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 110;

int n,m,d[N],q[N];
int h[N],e[N << 1],ne[N << 1],idx;

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 - 48;
		ch = getchar();
	}
	return x * f;
}

inline void add(int a,int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++;
}

inline void 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; i = ne[i] ) {
			int j = e[i];
			-- d[j];
			if (!d[j]) q[++ tt] = j;
		}
	}
}

signed main() {
	memset(h,-1,sizeof h);
	n = read();
	for (int i = 1; i <= n; ++ i ) {
		int a;
		while (cin >> a && a) add(i,a),++ d[a];
	}
	topsort();
	for (int i = 0; i < n; i ++ ) cout << q[i] << " ";
	return 0;
}

这里我是用的手写队列，当然你可以用 \(\text{STL}\)。

练习

接下来谈几道比较经典的题目。

1. P1983 [NOIP2013 普及组] 车站分级 ，这道题就是跑一遍拓扑排序，然后求个最短路就好，代码就不放了。

2. P3243 [HNOI2015]菜肴制作 ，此题强烈推荐做一做，做后会有比较大的收获。同样是先跑，然后在跑的时候求要求的值就好。

作者：\(\text{songszh}\)