拓扑排序

定义

拓扑排序要解决的问题是如何给一个有向无环图的所有节点排序。

用通俗点的话来描述这个概念，假设有三门课，高等数学-1，高等数学-2，高等数学-3，要想学高等数学-2，就得先学会高等数学-1，同理想学高等数学-3，就得学会高等数学-2。这三门课相当于三个顶点，对应的顺序就像是点与点之间的有向边。

如果要求想学高等数学-1，必须得学会高等数学-3，此时图中就出现了环，没法搞清先学哪个，无法进行拓扑。

所以如果有向图中存在环路，我们就没办法进行拓扑排序。

解决方案

我们用 Kahn 算法来解决拓扑排序问题。

过程

初始，有一个集合 S，其中装着所有入度为 0 的点，然后 L 是一个空列表。

每次从 S 中取出一个点 u（可以任意取），先将 u 放入 L，然后把边（u，x）（x 为 u 能到达的任意节点）删掉。

如果删除过程中某点 x 的入度变为 0，将其放入 S 中。

不断重复，直到 S 为空。检查图中是否还存在边，如果存在，则图中有环，否则 L 即为拓扑排序的结果。

代码

 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


int n, m;
vector<int> G[1010];
int in[1010];  // 存储每个结点的入度

bool toposort() {
    vector<int> L;
    queue<int> S;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) S.push(i); //入度为 0 的点进入 S 中
    while (!S.empty()) {
        int u = S.front();
        S.pop();
        L.push_back(u); //把 u 放入 L 中
        for (auto v : G[u]) { //遍历以 u 为起点的所有边
            if (--in[v] == 0) { //这里可以把 -- in[v] 放到外面，这样写是为了代码简洁。  
                S.push(v);
            }
        }
    }
    if (L.size() == n) { //如果 L 中存放了 n 个点，拓扑成功，输出排序结果  
        for (auto i : L) cout << i << ' ';
        return true;
    }
    return false; //否则图中有环，拓扑排序失败
}

时间复杂度

时间复杂度为 $O(E+V)$。

应用

可以用于判断图上是否有环，图是否为一条链等。

例题

洛谷 P2712

题目描述

食品店里有 $n$ 个摄像头，这种摄像头很笨拙，只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店，为了不让摄像头拍下他们犯罪的证据，他们抢劫前的第一件事就是砸毁这些摄像头。

为了便于砸毁摄像头，松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号，一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。

现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头，如不能则输出还没砸掉的摄像头的数量。

输入

第 $1$ 行，一个整数 $n$，表示摄像头的个数。

第 $2$ 到 $n+1$ 行是摄像头的信息，包括：摄像头的位置 $x$，以及这个摄像头可以监视到的位置数 $m$，之后 $m$ 个数 $y$ 是此摄像头可以监视到的位置。(砸了这些摄像头之后自然这些位置就监视不到了)

输出

若可以砸掉所有摄像头则输出“ $\texttt{YES}$ ”，否则输出还没砸掉的摄像头的数量。（不带引号）

样例

输入

输出

1

2

解题

读题后可以明确使用拓扑排序来解决问题，因为摧毁要有顺序，我们只能摧毁当前没被其他摄像头照到的，即入度为 0 的摄像头。

所以先找到当前入度为 0 的摄像头，赛到 S 中，再按照上面讲的，一直重复操作，直到 S 为空。

最后判断有多少个摄像头赛到过 S 中即可。

 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


#include <bits/stdc++.h>
using namespace std;

int n,m,in[10001],ans,vis[10001],a[10001];
vector<int>g[10001];

void TopoSort(){
    queue<int>s;
    ans=0;
    for(int i=1;i<=n;i++){
        if(!in[a[i]] && vis[a[i]])
            s.push(a[i]);
    }
    while(!s.empty()){
        int u = s.front();
        ans++;
        s.pop();
        for(auto v:g[u]){
            if(--in[v]==0&&vis[v])s.push(v);
        }
    }
    if(ans==n)cout<<"YES\n";
    else cout<<n-ans<<endl;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int m;
        cin>>a[i]>>m;
        vis[a[i]]=1;
        for(int j=1;j<=m;j++){
            int y;
            cin>>y;
            g[a[i]].push_back(y);
            in[y]++;
        }
    }
    TopoSort();
    return 0;
}