定义
拓扑排序
在一个 DAG（有向无环图） 中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 \({u}\) 到 \({v}\) 的有向边 \({(u,v)}\), 都可以有 \({u}\) 在 \({v}\) 的前面。
还有给定一个 DAG，如果从 \({i}\) 到 \({j}\) 有边，则认为 \({j}\) 依赖于 \({i}\)。如果 \({i}\) 到 \({j}\) 有路径（\({i}\) 可达 \({j}\)），则称 \({j}\) 间接依赖于 \({i}\)。
拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。
补充
\({\large 关于AOV网}\)
在日常生活中，一项大的工程可以看作是由若干个子工程（这些子
工程称为“活动” ）组成的集合，这些子工程（活动）之间必定存在
一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）
完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）
之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后
关系为有向边，这种有向图称为“顶点活动网络”
，又称“AOV网”。
在AOV网中，有向边代表子工程（活动）的先后关系，我们把一
条有向边起点的活动成为终点活动的前驱活动，同理终点的活动称
为起点活动的后继活动。而只有当一个活动全部的前驱全部都完成
之后，这个活动才能进行。例如在上图中，只有当工程1完成之后，
工程2、3、4、5、6才能开始进行。只有当2、3、4全部完成之后，7
才能开始进行。
一个AOV网必定是一个有向无环图，即不应该带有回路。否则，
会出现先后关系的自相矛盾。
上图就是一个出现环产生自相矛盾的情况。4是1的前驱，想完
成1，必须先完成4。3是4的前驱，而2是3的前驱，1又是2的前驱。
最后造成想完成1，必须先完成1本身，这显然出现了矛盾。
板板
板板
int n, m; //结点数和边数
vector<int> G[MAXN]; //存图
int in[MAXN]; // 存储每个结点的入度
//拓扑排序
bool toposort() {
vector<int> ans;
queue<int> q;
//入度为0的点入队
for (int i=1; i<=n; i++) {
if(in[i]==0){
q.push(i);
}
}
while (!q.empty()) {
int u=q.front();
q.pop();
ans.push_back(u);
for (auto v:G[u]) { //所有邻接点入度减1
in[v]--;
if(in[v]==0) { //入度变为0，则入队
q.push(v);
}
}
}
if(ans.size()==n){ //不存在环，输出序列
for (auto i:ans){
cout<<i<<' ';
}
return true;
}
else{ //存在环
return false;
}
}
例题
家谱树
问题描述
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
输入格式:
第1行一个整数N（1<=N<=100），表示家族的人数。
接下来N行，第I行描述第I个人的儿子。
每行最后是0表示描述完毕。
输出格式:
输出一个序列，使得每个人的后辈都比那个人后列出。
如果有多解输出任意一解。
样例输入:
5
0
4 5 1 0
1 0
5 3 0
3 0
样例输出:
2 4 5 3 1
思路
纯纯板子题
code
code
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define ll long long
#define inf 0x3f3f3f3f
#define Elaina 0
int a[N][N],ans[N];
queue <int> q;
int n,m;
void toposort(){
for(int i=1;i<=n;i++){
if(!ans[i]){
q.push(i);
}
}
while(!q.empty()){
int k=q.front();
q.pop();
cout<<k<<" ";
for(int i=1;i<=n;i++){
if(a[k][i]){
ans[i]--;
a[k][i]=0;
if(!ans[i]){
q.push(i);
}
}
}
}
return ;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
while(1){
cin>>m;
if(!m){
break;
}
a[i][m]=1;
ans[m]++;
}
}
toposort();
return Elaina;
}
AC代码
int main(){}
这个真的可以过（在HZOI题库里） 我没骗你
都看到这了，真的不点个赞吗(>ω<*)