简介

给出 $n$ 个元素的 $m$ 组关系：$a>b,$$a>c,$$b>c,$$b>d,$$\cdots$，试将 $n$ 个元素按大小排序。

将上述关系转化为有向图，$a\to b$ 代表 $a>b$。这种反映节点大小关系的图称作 AOV 网。

拓扑排序求的是符合条件的优先顺序，即拓扑序列。

原理

根据定义，没被箭头指着的节点（即入度为 $0$ 的节点）是当前最大的节点。

节点 $a$ 的入度为 $0$。在拓扑序列中追加 $a$，并删除 $a$ 和它的所有邻边。 拓扑序列：$a$。

节点 $e$ 的入度为 $0$。在拓扑序列中追加 $e$，并删除 $e$ 和它的所有邻边。 拓扑序列：$a,$$e$。

节点 $b$ 的入度为 $0$。在拓扑序列中追加 $b$，并删除 $b$ 和它的所有邻边。 拓扑序列：$a,$$e,$$b$。

节点 $c$ 的入度为 $0$。在拓扑序列中追加 $c$，并删除 $c$ 和它的所有邻边。 拓扑序列：$a,$$e,$$b,$$c$。

节点 $d$ 的入度为 $0$。在拓扑序列中追加 $d$，并删除 $d$ 和它的所有邻边。 拓扑序列：$a,$$e,$$b,$$c,$$d$。

节点 $f$ 的入度为 $0$。在拓扑序列中追加 $f$，并删除 $f$ 和它的所有邻边。 拓扑序列：$a,$$e,$$b,$$c,$$d,$$f$。

故样例的一种拓扑序列为 $a,$$e,$$b,$$c,$$d,$$f$。

INFO

同一张 AOV 网可能有多个拓扑序列。

1. 定义一个队列，用于存放节点；
2. 将所有入度为 $0$ 的节点入队；
3. 取出队头的节点，并删除它的所有出边.若出现入度为零的节点，将其入队。

拓扑排序结束时，若拓扑序列未包含全部节点，则剩下的节点形成了闭环。此时不存在拓扑序列。

时间复杂度为 $O(n+$$m)$。

const int N = 1e6;
int n, deg[N];    // deg[u]: u 的入度
vector<int> g[N]; // g[u]: u 的邻接点集合
vector<int> vec;  // vec: 拓扑序列

// 预处理所有节点的入度
void pre() {
    memset(deg, 0, sizeof deg);
    for (int u = 1; u <= n; u ++)
        for (int v : g[u])
            deg[v] ++;
}

void topSort() {
    pre();
    vec.clear();
    for (int i = 1; i <= n; i ++)
        if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vec.push_back(u);
        for (int v : g[u])
            if (! -- deg[v]) // 出现新的节点入度为 0
                q.push(v);
    }
    if (vec.size() != n) // 不存在拓扑序列
        vec.clear();
}