拓扑排序 Topological Sort

在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u,v)$ , 都可以有 $u$ 在 $v$ 的前面。

算法

可以简单地用DFS来解决，时间复杂度 $O(E+V)$ ，空间复杂度 $O(V)$ 。

也可以用BFS来解（Kahn算法）：基本思路就是找到入度为0的节点加到队列中，进行访问。每访问一个节点，将其出发的边都去掉，如果因此得到更多入度为0的节点，则也加入队列中。由此得到的节点访问顺序，就是拓扑排列序。

习题

习题
P1113		杂务		普及/提高-
P4376	USACO Gold	Milking Order	2018	提高+/省选-	解答

BFS求拓扑排序

使用拓扑排序Kahn算法的解法如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
 
#define ll long long
 
using namespace std;
 
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}
 
const int N=500005;
 
int ind[N],f[N],a[N];  //ind--入度   f--答案   a--时间
vector <int> edge[N];
queue <int> q;
 
int main() {
	int n=read();
	for (int i=1;i<=n;i++) {
		int x=read();
		a[i]=read();
		while (int y=read()) {
			if (!y) break;
			edge[y].push_back(x);
            ind[x]++;
		}
	}
    //收集所有入度为0的节点
	for (int i=1;i<=n;i++) {
		if (ind[i]==0) {
			q.push(i);
			f[i]=a[i];
		}
	};
	while (!q.empty()) {
		int rhs=q.front();
		q.pop();
        //去掉相邻边，再找出所有入度为0的节点
		for (int i=0;i<edge[rhs].size();i++) {
			int u=edge[rhs][i];
			ind[u]--;
			if (ind[u]==0) q.push(u);
			f[u]=max(f[u],f[rhs]+a[u]);
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++) {
		ans=max(ans,f[i]);   //统计答案
	}
	printf("%d\n",ans);
	return 0;
}

DFS求拓扑排序

拓扑排序也可以用DFS来求：

vector<int> G[MAXN];  // vector 实现的邻接表
int c[MAXN];          // 标志数组
vector<int> topo;     // 拓扑排序后的节点
 
bool dfs(int u) {
  c[u] = -1;
  for (int v : G[u]) {
    if (c[v] < 0)
      return false;
    else if (!c[v])
      if (!dfs(v)) return false;
  }
  c[u] = 1;
  topo.push_back(u);
  return true;
}
 
bool toposort() {
  topo.clear();
  memset(c, 0, sizeof(c));
  for (int u = 0; u < n; u++)
    if (!c[u])
      if (!dfs(u)) return false;
  reverse(topo.begin(), topo.end());
  return true;
}