拓扑排序

引入

拓扑排序是一个有向无环图的所有顶点的线性序列。

该序列需要满足每个顶点出现且只出现一次和如果有一条 $A$ 到 $B$ 的路径，在序列中 $A$ 出现在 $B$ 的前面。。

实现

拓扑排序的步骤：

• 计算每个点的入度。
• 入度为 $0$ 就加入队列。
• 当队列不为空则循环：
  • 取出队首元素并输出。
  • 遍历队首元素的连边，对应节点的入度 $-1$。
  • 当对应的节点入度为 $0$ 就加入队列。

例题

洛谷 B3644【模板】拓扑排序 / 家谱树

题目描述

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。

输入格式

第 $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;
}