拓扑排序
简介 #
给出 $n$ 个元素的 $m$ 组关系：$a > b,a > c,b > c,b > d,\cdots$，试将这 $n$ 个元素按大小排序.
将上述关系转化为有向图，$a → 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$.
同一张
AOV网可能有多个拓扑序列.
$deg[u]$：节点 $u$ 的入度，需要预处理.
-
定义一个队列，用于存放节点；
-
将所有入度为 $0$ 的节点入队；
-
取出队头的节点，并删除它的所有出边.若出现入度为零的节点，将其入队.
拓扑排序结束时，若拓扑序列未包含全部节点，则剩下的节点形成了闭环.此时不存在拓扑序列.
时间复杂度为 $O(n+m)$.
const int N = 1e6;
int n, deg[N];
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 i = 0; i < g[u].size(); i ++)
deg[g[u][i]] ++;
}
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 i = 0; i < g[u].size(); i ++)
if(! -- deg[g[u][i]]) // 出现新的节点入度为 0
q.push(g[u][i]);
}
if(vec.size() != n) // 不存在拓扑序列
vec.clear();
}