拓扑排序 Topological Sort

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

算法

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

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

习题

• P1113 杂务

使用拓扑排序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;
}