拓扑排序学习笔记
忘了学没学过了，就当没学过吧
推歌：Oliver《D.S.》
B 站以外好像没有能听的
概念
拓扑排序的要求：有向无环图（TAG图）。
拓扑序列中，一条有向边的起点一定排在它的重点的前面。
由此可得拓扑序列求法：每次找到入度为 \(0\) 的点，把它加入序列中；删除它和由它出发的边，然后重复以上操作。
实现
Kahn 算法是一种 \(O(n+m)\) 复杂度实现上述过程的算法。
它的中心思想是用队列存下当前入度为 \(0\) 的点，然后由队首的点进行遍历。
展开代码
//top数组也可以考虑使用动态数组
void topsort() {
tot = 0;
queue<int> q;
for(int i = 1; i <= n; ++i) if(!ind[i]) q.push(i);
while(!q.empty()) {
int ft = q.front();
q.pop();
top[++tot] = ft;
for(int i = head[ft]; i; i = nxt[i]) {
int x = to[i];
--ind[x];
if(!ind[x]) q.push(x);
}
}
}
例题
B3644 家谱树
这题什么时候到 B 题库了
简单模板，注意处理输入：
接下来 \(N\) 行，第 \(i\) 行描述第 \(i\) 个人的后代编号 \(a_{i,j}\), 表示 \(a_{i,j}\) 是 \(i\) 的后代。每行最后是 \(0\) 表示描述完毕。
以及别犯低级错误：
展开代码
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int n, a, head[N], to[N], nxt[N], ind[N], top[N], tot;
void add(int u, int v) {
to[++tot] = v;
nxt[tot] = head[u];
head[u] = tot;
++ind[v];
}
void topsort() {
tot = 0;
queue<int> q;
for(int i = 1; i <= n; ++i) if(!ind[i]) q.push(i);
while(!q.empty()) {
int ft = q.front();
q.pop();
top[++tot] = ft;
for(int i = head[ft]; i; i = nxt[i]) {
int x = to[i];
--ind[x];
if(!ind[x]) q.push(x);
}
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
while(1){
scanf("%d", &a);
if(!a) break;
add(i, a);
}
}
topsort();
for(int i = 1; i <= n; ++i) printf("%d ", top[i]);
return 0;
}