5.8.5 拓扑排序

将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。它的思想是，每次取出图上不被依赖的点，同时删去与这些点相连的边，更新图上的依赖关系，直到没有点可以被取出。

拓扑排序也用于发现图上的环，这些节点相互依赖，不会出现在排序结果当中。

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10004;
vector<int> g[N];
vector<int> ans;
int indegree[N];
int n, m;
bool TopologicalSort() {
    queue<int> q;
    for (int i=1; i<=n; ++i) {
        if (indegree[i] == 0) {            // 入度为 0 的节点不被依赖
            q.push(i);
            ans.push_back(i);
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i=0; i<g[x].size(); ++i) {    // 遍历所有出边的终点
            int y = g[x][i];
            if (--indegree[y] == 0) {        // 删除边，使终点入度减 1
                q.push(y);                    // 入度为 0 的节点不被依赖
                ans.push_back(y);
            }
        }
    }
    return ans.size() == n;
}
int main() {
    cin >> n >> m;
    for (int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        ++indegree[y];        // 有向图
    }
    if (TopologicalSort()) {
        for (int i=0; i<n; ++i) {
            cout << ans[i] << endl;
        }
    } else {
        cout << "Cycle deteted." << endl;
    }
    return 0;
}

时间复杂度：#card=math&code=O%28n%20%2B%20m%29&id=tm5sm)， 为点数， 为边数

例题：蓝桥 发现环【第八届】【决赛】

用拓扑排序解决发现环的问题再适合不过。题目要求输出环上的点。与模板稍有出入的是，这里的图是一张无向图。在无向图上，我们关于「依赖」的考虑需要稍稍变化——在无向图的环上，所有节点至少与其他两个节点相连，也就是说，它的度保证不小于 2 。如果找到一个节点的度为 1，那么它不在环上。

在经历了最短路的学习后，你应该对这些图的基本操作有一定的了解，可以自如地调整模板。

参考代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 100004;
vector<int> g[N];
int deg[N];
bool vis[N];
int n;
void toposort() {
    queue<int> q;
    for (int i=1; i<=n; ++i) {
        if (deg[i] == 1) {            // 度为 1 的节点不被依赖
            q.push(i);
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = true;
        for (int i=0; i<g[x].size(); ++i) {
            int y = g[x][i];
            if (--deg[y] == 1) {
                q.push(y);            // 度为 1 的节点不被依赖
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
        ++deg[x];
        ++deg[y];
    }
    toposort();
    bool head = true;
    for (int i=1; i<=n; ++i) {
        if (!vis[i]) {
            if (!head) cout << " ";        // 严谨输出，行末不留空格
            else head = false;
            cout << i;
        }
    }
    cout << endl;
    return 0;
}