前言:
蓝桥杯的时间快到了，我全心学习算法的日子快到头了，其实学习算法还是挺好玩的。
言归正传，今日浅浅地复习一下拓扑排序，还是挺容易的，只要明白其内涵便可以快速AC。
概述:
拓扑排序主要用来解决有向图中的依赖解析问题。
即：对于任何有向图而言，其拓扑排序为其所有节点的一个线性排序(对于同一个有向图而言可能存在多个这样的结点排序)。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v,则在拓扑排序u一定出现在v的前面。
这里引入一个概念——入度，即该结点被其他结点连接的数量(是从其他结点指向该节点）。
而找到入度为0的点，同时把该点连接的其他结点的边删去，同时连接的结点入度减去1，
再继续找入度点为0的点,重复该循环，直到所有的点都入度为0；
注:只有有向非环图才存在拓扑排序
解决拓扑排序问题主要分为两个步骤:
1.vector存图(还可以用其他方法存图，例如邻接表，邻接矩阵）
1
2
3
4
| void cuntu(int x,int i){
in[x]++;//x的入度数加1
e[i].push_back(x);//x为i的后辈
}
|
2.利用队列bfs找入度为0的结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| for(int i=1;i<=n;i++){
if(!in[i]){
q.emplace(i);//先找到入度为0的点塞进队列中
}
}
while(q.size()){//利用bfs继续寻找入度为0的点
int t=q.front();
q.pop();//将入度为0的点删去。
for(int i=0;i<e[t].size();i++){//遍历被删去的点的所有边（指向别的结点）
int tmp=e[t][i];
in[tmp]--;//删去有向边，同时被指向的结点，入度-1。
if(!in[tmp]){//判断是否有删去有向边后有入度为0的点
q.emplace(tmp);
}
}
}
|
实践
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
using namespace std;
const int N=105;
int in[N],n,x;
vector<int>e[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
while(x){
in[x]++;
e[i].push_back(x);
cin>>x;
}
}
queue<int>q;
for(int i=1;i<=n;i++){
if(!in[i]){
cout<<i<<" ";
q.emplace(i);
}
}
while(q.size()){
int t=q.front();
q.pop();
for(int i=0;i<e[t].size();i++){
int tmp=e[t][i];
in[tmp]--;
if(!in[tmp]){
cout<<tmp<<" ";
q.emplace(tmp);
}
}
}
return 0;
}
|
