Appearance
简介
给出
将上述关系转化为有向图,
拓扑排序求的是符合条件的优先顺序,即拓扑序列。
原理
根据定义,没被箭头指着的节点(即入度为
节点 拓扑序列:
故样例的一种拓扑序列为
同一张 AOV 网可能有多个拓扑序列。
- 定义一个队列,用于存放节点;
- 将所有入度为
的节点入队; - 取出队头的节点,并删除它的所有出边.若出现入度为零的节点,将其入队。
拓扑排序结束时,若拓扑序列未包含全部节点,则剩下的节点形成了闭环。此时不存在拓扑序列。
时间复杂度为
cpp
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();
}