定义

在图论中，拓扑排序是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足以下两个条件：

1. 每个顶点出现且仅出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 必然出现在顶点 B 之前。

只有 DAG 才存在拓扑排序。

应用

可以很方便的遍历存在多个根节点的 DAG，且每个节点遍历且仅遍历一次。

可以方便的找到最长路径，用个 dp 数组即可。

实现

类似于 bfs 的实现方式？也可以看作一种特殊的 bfs。使用 queue 将所有入度为 0 的节点加入队列并更新入度，保证每次加入队列的节点的入度均为 0。

// 建图，同时注意入度的统计
void add(int u, int v) {
    ind[v]++;
    Next[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    cnt++;
}
// 根据入度将根节点加入队列
for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            q.push(i);
        }
    }
// bfs遍历
 while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int e = head[u]; e > 0; e = Next[e]) {
            int v = to[e];
            ind[v]--;
            if (ind[v] == 0)
                q.push(v);
        }
    }

……还算简单？