拓扑排序
引入
拓扑排序是一个有向无环图的所有顶点的线性序列。
该序列需要满足每个顶点出现且只出现一次和如果有一条 AA 到 BB 的路径，在序列中 AA 出现在 BB 的前面。
实现
拓扑排序的步骤：
- 计算每个点的入度。
- 入度为 \(0\) 就加入队列。
- 当队列不为空则循环：
- 取出队首元素并输出。
- 遍历队首元素的连边，对应节点的入度 \(-1\)。
- 当对应的节点入度为 \(0\) 就加入队列。
例题
题目描述
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。
输入格式
第 \(1\) 行一个整数 \(N\)（\(1 \le N \le 100\)），表示家族的人数。接下来 \(N\) 行，第 \(i\) 行描述第 \(i\) 个人的后代编号 \(a_{i,j}\)，表示 \(a_{i,j}\) 是 \(i\) 的后代。每行最后是 \(0\) 表示描述完毕。
输出格式
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。
#include <iostream>
#include <queue>
#define MAXN 105
using namespace std;
int n, t;
struct edge{int to, nxt;}e[MAXN * MAXN];
int head[MAXN], cnt = 1, rd[MAXN];
queue <int> q;
queue <int> ans;
bool flag;
void add(int u, int v){
cnt++;e[cnt].to = v;e[cnt].nxt = head[u];head[u] = cnt;
}
int main(){
cin >> n;
for(int i = 1 ; i <= n ; i ++)
do{cin >> t;add(i, t),rd[t]++;}while(t != 0);
for(int i = 1 ; i <= n ; i ++)
if(rd[i] == 0)q.push(i), ans.push(i);
while(!q.empty()){
t = q.front();q.pop();
for(int i = head[t] ; i != 0 ; i = e[i].nxt){
int v = e[i].to;rd[v]--;
if(rd[v] == 0)q.push(v),ans.push(v);
}
}
while(!ans.empty() && ans.front() != 0){
t = ans.front();ans.pop();
if(flag == true)putchar(' ');
cout << t;flag = true;
}
cout << endl;return 0;
}