拓扑排序学习笔记

上图的拓扑序为：

ABCD 或 ACBD

也就是说，一个AOV网络（有向无环图DAG）的拓扑序列不是唯一的

 存在回路，不能求出拓扑排序

拓扑排序步骤

1、从有向图中选取一个没有前驱（入度为0）的顶点，并输出；

2、从有向图中删除该顶点以及所有它指向的边；

3、重复上述步骤，直到图空；或者图不空，但找不到入度为0的顶点。

……

1）点a和b的入度都为0，我们选择b；

2）删除b后，在剩下的入度为0的点中，我们选择h；

3）删除h后，选择入度为0的点a；

4）……，最后得到一个拓扑序为：bhacdgfe

应用：

利用拓扑序可以判断一个有向图是否含环（回路）：

一，有向图的拓扑序列

题目描述

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 -1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 -1。

样例输入1

3 3
1 2
2 3
1 3

样例输出1

1 2 3

注释说明

1≤n,m≤1e5

#include<bits/stdc++.h>
using namespace std;
vector<int>a[100005];
queue<int> q;
int n,m,x,y,rd[100003],tp[100003],k;
int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);a[x].push_back(y);rd[y]++;}for(int i=1;i<=n;i++){if(rd[i]==0){q.push(i);}}while(!q.empty()){int now=q.front();tp[++k]=now;q.pop();for(int i=0;i<a[now].size();i++){int to=a[now][i];rd[to]--;if(rd[to]==0){q.push(to);}}}if(k<n){puts("-1");}else {for(int i=1;i<=k;i++){printf("%d ",tp[i]);}}
}

二，家谱树

题目描述

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

输入格式

第1行一个整数N（1<=N<=100），表示家族的人数。
接下来N行，第I行描述第I个人的儿子。
每行最后是0表示描述完毕。

输出格式

输出一个序列，使得每个人的后辈都比那个人后列出。
如果有多解输出任意一解。

样例输入1

5
0
4 5 1 0
1 0
5 3 0
3 0

样例输出1

2 4 5 3 1

代码

#include<bits/stdc++.h>
using namespace std;
vector<int>a[100005];
queue<int> q;
int n,m,x,rd[100003],tp[100003],k;
int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int j=0;for(;;j++){scanf("%d",&x);if(x==0)break;a[i].push_back(x);rd[x]++;}}for(int i=1;i<=n;i++){if(rd[i]==0)q.push(i);}while(!q.empty()){int now=q.front();tp[++k]=now;q.pop();for(int i=0;i<a[now].size();i++){int to=a[now][i];rd[to]--;if(rd[to]==0){q.push(to);}}}for(int i=1;i<=k;i++){printf("%d ",tp[i]);}}