【题目链接】

ybt 1351：【例4-12】家谱树
洛谷 B3644 【模板】拓扑排序 / 家谱树

【题目考点】

1. 拓扑排序

拓扑排序是一个有向无环图（DAG Directed acyclic graph）的所有顶点的线性序列。
拓扑排序序列要求：

1. 每个顶点出现且仅出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

拓扑排序的性质：

1. 一个有向无环图可以有一个或多个拓扑排序序列。
2. 如果在拓扑排序中顶点A在顶点B前，那么顶点A到顶点B可能有路径，顶点B到顶点A一定没有路径。

反过来：如果一个序列中后面的顶点到前面的顶点都没有路径，那么该序列是拓扑排序序列。

2. 求有向无环图的拓扑排序序列

(1) Kahn算法（常用）

1. 统计各顶点入度
2. 将入度为0的顶点入队
3. 每出队一个顶点，访问该顶点，并将该顶点“删去”。即该顶点的邻接点入度减1。如果该顶点入度变为0，访问并入队。
4. 重复上一步，直到队列为空。

如果在访问顶点时输出顶点编号，即可得到拓扑排序序列。
时间复杂度：$O(V+E)$，其中$V$是图的顶点数量，$E$为图的边的数量。

(2) Dfs算法

图的后序遍历序列：dfs过程中，对于每个顶点，在访问该顶点的所有邻接点后，最后再输出该顶点的编号，可以得到图的后序遍历序列。
图中如果从顶点A到顶点B有一条路径，那么在图的后序遍历序列中，一定会先输出顶点B，再输出顶点A，顶点B在顶点A前。
如果取后序遍历序列的逆序列，即逆后序遍历序列，如果顶点A到顶点B有一条路径，那么该序列中顶点A在顶点B前。
因此有向无环图的逆后序遍历序列就是拓扑排序序列。
具体实现：在dfs的过程中，在访问一个顶点的所有邻接点后，将当前顶点入栈。最后出栈输出，就可以得到该图的逆后序遍历序列。
时间复杂度：$O(V+E)$，其中$V$是图的顶点数量，$E$为图的边的数量。

【解题思路】

每个人是一个顶点。如果a是b的父辈，那么有一条从a到b的有向边<a, b>。
本题所求序列中“每个人的后辈都比那个人后列出”。
本题中，如果a到b有一条路径，说明b是a的后辈，在拓扑排序序列中b在a的后面。
因此求该图的拓扑排序序列，就可以满足题目要求。

【题解代码】

解法1：Kahn算法

• 写法1：使用邻接表

#include<bits/stdc++.h>
using namespace std;
#define N 105
vector<int> edge[N];
int n, t, deg[N];
void topoSort()
{
	queue<int> que;
	for(int i = 1; i <= n; ++i)
		if(deg[i] == 0)
			que.push(i);
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		cout << u << ' ';
		for(int v : edge[u])
			if(--deg[v] == 0)
				que.push(v);
	}
}
int main()
{
	cin >> n;
	for(int f = 1; f <= n; ++f)
		while(cin >> t && t != 0)
		{
			edge[f].push_back(t);
			deg[t]++;
		}
	topoSort();
	return 0;
}

• 写法2：使用邻接矩阵

#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, t, edge[N][N], deg[N];//deg[i]:顶点i的入度 
void topoSort()//拓扑排序 
{
	queue<int> que;
	for(int i = 1; i <= n; ++i) if(deg[i] == 0)
		que.push(i);
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		cout << u << ' ';
		for(int v = 1; v <= n; ++v) if(edge[u][v])
			if(--deg[v] == 0)
				que.push(v);
	}
}
int main()
{
	cin >> n;
	for(int f = 1; f <= n; ++f)
		while(cin >> t && t)
		{
			edge[f][t] = 1;
			deg[t]++;
		}
	topoSort();
	return 0;
}

解法2：Dfs算法

#include<bits/stdc++.h>
using namespace std;
#define N 105
vector<int> edge[N];
int n;
bool vis[N];
stack<int> stk;
void dfs(int u)
{
	vis[u] = true;
	for(int v : edge[u]) if(!vis[v])
		dfs(v);
	stk.push(u);
}
int main()
{
	int f, t;
	cin >> n;
	for(f = 1; f <= n; ++f)
		while(cin >> t && t != 0)
			edge[f].push_back(t);
	for(int i = 1; i <= n; ++i) if(!vis[i])
		dfs(i);
	while(!stk.empty())
	{
		cout << stk.top() << ' ';
		stk.pop();
	}
	return 0;
}