拓扑排序

拓扑的概念（不重要）

知乎上又一篇科普：硬核科普：什么是拓扑？ - 知乎

拓扑学（Topology）原名叫做位置分析（Analysis situs），是研究图形（或集合）在连续变形下的不变的整体性质的一门几何学。由于早期研究的是直观拓扑学，因此人们又把这种研究连续变换下不变的性质的学科形象地称为“橡皮几何学”或“橡皮膜上的几何学”，也就是说橡皮膜在不被弄破的情况下，不管如何拉伸、压缩、扭转等变形而存在着某些不变的性质。因此，研究这些不变性成为拓扑学研究的中心课题。中文“拓扑学”一词最早由陈省身根据英文Topology音译而来。

简单一句话概括：拓扑学就是解决图形或集合的整体性质的一门几何学

拓扑排序

定义：拓扑排序（Topological sorting）要解决的问题是如何给一个有向无环图的所有节点排序。

图论中的拓扑排序，就是用来理清图上各个点的先后关系，对应着实际生活中的一些事件的依赖关系

比如：

• 吃饭的前置条件是有饭吃，所以它依赖于前置事件去食堂买饭、订外卖、出去下馆子、泡方便面等这类前置事件
• 参加ICPC区域赛的条件是，能找到另外两个队友跟自己组队，报了名，交了报名费，在比赛日按时到达赛场，这4个条件必须全都满足，才能在赛场上打比赛

拓扑排序就是找到对于某个事件，哪些事件是必须发生在它前面的，对于这种先后关系的一种排序算法

拓扑排序跟大小无关，而跟先后顺序有关

更加详细的介绍可以参考OI-Wiki：拓扑排序 - OI Wiki

Kahn 算法（重要）

过程

初始状态下，集合 $S$ 装着所有入度为 $0$ 的点，$L$ 是一个空列表。

每次从 $S$ 中取出一个点 $u$（可以随便取）放入 $L$, 然后将 $u$ 的所有边 $(u, v_1), (u, v_2), (u, v_3) \cdots$ 删除。对于边 $(u, v)$，若将该边删除后点 $v$ 的入度变为 $0$，则将 $v$ 放入 $S$ 中。

不断重复以上过程，直到集合 $S$ 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 $L$，$L$ 中顶点的顺序就是构造拓扑序列的结果。

伪代码

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

例题

P1113 杂务 - 洛谷 | 计算机科学教育新生态

const int N = 1e5 + 10;

int n, m;
std::vector<int> g[N];
int len[N], cost[N];
int din[N];

void topsort() {
    std::queue<int> q;
    for (int i = 1; i <= n; i ++ ) {
        if (!din[i]) {
            q.push(i);
            cost[i] = len[i];
        }
    }

    while (q.size()) {
        int u = q.front();
        q.pop();

        for (auto v: g[u]) {
            cost[v] = std::max(cost[v], cost[u] + len[v]);
            if (--din[v] == 0) {
                q.push(v);
            }
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        int id, x;
        cin >> id >> len[i];
        while (cin >> x, x) {
            g[x].push_back(i);
            din[i] ++;
        }
    }

    topsort();

    int ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        ans = std::max(ans, cost[i]);
    }
    cout << ans << "\n";
}