【洛谷B3644】【模板】拓扑排序 / 家谱树解题报告

2024-07-16 01:06:03
开发
20

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

题目描述

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

输入格式

第 $1$ 行一个整数 $N$ （ $\le N \le 100$ ），表示家族的人数。接下来 $N$ 行，第 $i$ 行描述第 $i$ 个人的后代编号 $a_{i,j}$ ，表示 $a_{i,j}$ 是 $i$ 的后代。每行最后是 $0$ 表示描述完毕。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

2 4 5 3 1

这题非常非常简单，就是一个拓扑排序模板题。
题目直接告诉你每个人的后代，其实就是每个顶点的直接后继，然后求这个图的拓扑排序序列。
关于拓扑排序的详细讲解，请看我这篇博客：图的应用3-有向无环图、拓扑排序
我一共写了三种做法，全都 $A C$ ，足见其简单，而且这题数据范围也很友好，邻接矩阵可以放心食用。
首先是邻接矩阵实现，完整代码如下：

//AC(100pts)
#define _CRT_SECURE_NO_WARNINGS 1
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 114;
int n, indegree[N], print[N];//顶点数，各点入度，拓扑序列数组
bool A[N][N];//邻接矩阵存图

inline void Init() {
	cin >> n;
	for (int i = 0; i <= n; ++i) {//初始化
		indegree[i] = 0;
		for (int j = 0; j <= n; ++j) {
			A[i][j] = false;
		}
	}
	for (int i = 1, j; i <= n; ++i) {
		for (int k = 0; k <= n; ++k) {
			cin >> j;
			if (!j)break;//读到0结束当前顶点的后代读入
			A[i][j] = true;//邻接矩阵加入有向边
			indegree[j]++;//后代的入度加1
		}
	}
	return;
}

inline bool TopologicalSort() {//拓扑排序
	int Sta[N], top = 0, count = 0;//静态数组模拟栈
	memset(Sta, 0, sizeof(Sta));//初始化栈
	int i;
	for (i = 1; i <= n; ++i)
		if (!indegree[i])Sta[++top] = i;//入度为0的顶点入栈
	while (top) {
		i = Sta[top--];//栈顶元素出栈
		print[++count] = i;//输出i
		for (int j = 1; j <= n; ++j)
			if (A[i][j]) {//若i到j直接存在一条边
				A[i][j] = false, indegree[j]--;//删除该边，j的入度减1
				if (!indegree[j])Sta[++top] = j;//若j的入度减为0，则入栈
			}
	}
	if (count < n)return false;//若计数小于顶点数，说明存在环
	else return true;//否则拓扑排序成功
}

int main() {
	Init();
	if (!TopologicalSort())cout << "Error!" << endl;//排序失败
	else {//排序成功
		for (int i = 1; i <= n; ++i)
			cout << print[i] << " ";//输出拓扑排序序列
		cout << endl;
	}
	return 0;
}

邻接矩阵的完整代码也可看我的Github：传送门

（ $↑$ 内附赠逆拓扑排序实现代码）

然后是邻接表实现，之前我贴的讲解博客里有各函数的拆分讲解。
完整代码如下：

//AC(100pts)
#define _CRT_SECURE_NO_WARNINGS 1
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define MaxVertexNum 114
typedef struct ArcNode {
	int adjvex;
	struct ArcNode* nextarc;
}ArcNode, * ArcList;
typedef struct VNode {
	int data;
	ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

int indegree[MaxVertexNum], print[MaxVertexNum];
//记录各点入度，记录拓扑排序序列

inline void Init(ALGraph& G) {//预处理
	for (int i = 1; i <= G.vexnum; ++i) {
		ArcList h = (ArcList)malloc(sizeof(ArcList));
		h->adjvex = 0;
		h->nextarc = NULL;
		G.vertices[i].data = 0;
		G.vertices[i].firstarc = h;
	}
	memset(indegree, 0, sizeof(indegree));
	memset(print, 0, sizeof(print));
	return;
}

inline void AG_Insert(ALGraph& G, int i, int j) {//头插法加入边
	ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex = j;
	ArcNode* head = G.vertices[i].firstarc;
	ArcNode* tail = G.vertices[i].firstarc->nextarc;
	p->nextarc = tail;
	head->nextarc = p;
	return;
}

inline bool Topologicalsort(ALGraph G) {
	int Sta[MaxVertexNum], top = 0, count = 0;
	//用静态数组模拟栈，top为栈顶指针，count为拓扑序列数组下表
	memset(Sta, 0, sizeof(Sta));
	int i;
	for (i = 1; i <= G.vexnum; ++i)
		if (!indegree[i])Sta[++top] = i;//将初始入度为0的顶点进栈
	while (top) {//当栈不空时
		i = Sta[top--];//栈顶元素出栈
		print[++count] = i;//输出顶点i
		for (ArcNode* p = G.vertices[i].firstarc; p != NULL; p = p->nextarc) {
			//将所有i指向的顶点入度减1，并将入度减为0的顶点压入栈Sta中
			int v = p->adjvex;
			if (!v)continue;
			if (!(--indegree[v]))
				Sta[++top] = v;//度为0则入栈
			p->adjvex = 0;//删除边
		}
	}
	if (count < G.vexnum)return false;//排序失败，图中存在回路
	else return true;//拓扑排序成功
}

int main() {
	ALGraph G;
	cin >> G.vexnum;
	Init(G);
	for (int i = 1, j; i <= G.vexnum; ++i) {
		for (int k = 0; k <= G.vexnum; ++k) {
			cin >> j;
			if (!j)break;
			AG_Insert(G, i, j);
			indegree[j]++;
		}
	}
	if (!Topologicalsort(G))cout << "No DAG!" << endl;
	else {
		for (int i = 1; i <= G.vexnum; ++i)
			cout << print[i] << " ";
		cout << endl;
	}
	return 0;
}

最后是邻接表的 $D FS$ 实现，预处理和基本操作函数之类的直接用上面的邻接表实现，原理详解请看之前我贴的讲解博客。
完整代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define MaxVertexNum 114
typedef struct ArcNode {
	int adjvex;
	struct ArcNode* nextarc;
}ArcNode, * ArcList;
typedef struct VNode {
	int data;
	ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

int indegree[MaxVertexNum], print[MaxVertexNum];
//记录各点入度，记录拓扑排序序列

inline void Init(ALGraph& G) {//预处理
	for (int i = 1; i <= G.vexnum; ++i) {
		ArcList h = (ArcList)malloc(sizeof(ArcList));
		h->adjvex = 0;
		h->nextarc = NULL;
		G.vertices[i].data = 0;
		G.vertices[i].firstarc = h;
	}
	memset(indegree, 0, sizeof(indegree));
	memset(print, 0, sizeof(print));
	return;
}

inline void AG_Insert(ALGraph& G, int i, int j) {//头插法加入边
	ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex = j;
	ArcNode* head = G.vertices[i].firstarc;
	ArcNode* tail = G.vertices[i].firstarc->nextarc;
	p->nextarc = tail;
	head->nextarc = p;
	return;
}

int tim, finishtime[MaxVertexNum];//计时变量，各顶点用时数组
bool visited[MaxVertexNum];//访问标记

inline void DFS(ALGraph G, int v) {
	visited[v] = true;
	for (ArcNode* p = G.vertices[v].firstarc->nextarc; p != NULL; p = p->nextarc) {
		int w = p->adjvex;//依次遍历当前顶点的邻边未访问的顶点
		if (!visited[w])DFS(G, w);
	}
	finishtime[v] = ++tim;//搜索深度越深，tim值越小
	//如果要输出逆拓扑排序序列，只需把这一行改为输出v即可
	return;
}

inline void DFSTravere(ALGraph G) {
	memset(visited, false, sizeof(visited));//初始化
	memset(finishtime, 0, sizeof(finishtime));
	tim = 0;
	for (int i = 1; i <= G.vexnum; ++i)//从第一个顶点开始深搜
		if (!visited[i])DFS(G, i);
	return;
}

int main() {
	ALGraph G;
	cin >> G.vexnum;
	Init(G);
	for (int i = 1, j; i <= G.vexnum; ++i) {
		for (int k = 0; k <= G.vexnum; ++k) {
			cin >> j;
			if (!j)break;
			AG_Insert(G, i, j);
			indegree[j]++;
		}
	}
	DFSTravere(G);//深搜
	int con = 0;//计数
	for (int i = 1; i <= G.vexnum; ++i) {
		int maxn = -1, maxm = 0;
		for (int j = 1; j <= G.vexnum; ++j)
			if (finishtime[j] > maxn)
				maxn = finishtime[j], maxm = j;
				//每次循环找到finishtime数组里tim值最大的顶点
		finishtime[maxm] = -1;//删除当前tim的最大值
		print[++con] = maxm;//输出当前tim值最大的顶点
	}
	for (int i = 1; i <= G.vexnum; ++i)
		cout << print[i] << " ";//输出拓扑排序序列
	cout << endl;
	return 0;
}

邻接表的两个实现完整代码也可以看我的Github：传送门

不过我没写判环操作，话说有环的话那就不是 $D A G$ 图了……

总之还是非常简单的一题，但是有点费时间了。
以上。

原文地址:https://blog.csdn.net/Engels_Si_Fish/article/details/140450970 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1812896419850358784.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部