【模板】拓扑排序 / 家谱树
题目描述
有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列,使得每个人的后辈都比那个人后列出。
输入格式
第 1 1 1 行一个整数 N N N( 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100),表示家族的人数。接下来 N N N 行,第 i i i 行描述第 i i i 个人的后代编号 a i , j a_{i,j} ai,j,表示 a i , j a_{i,j} ai,j 是 i i i 的后代。每行最后是 0 0 0 表示描述完毕。文章来源:https://www.toymoban.com/news/detail-822252.html
输出格式
输出一个序列,使得每个人的后辈都比那个人后列出。如果有多种不同的序列,输出任意一种即可。文章来源地址https://www.toymoban.com/news/detail-822252.html
样例 #1
样例输入 #1
5
0
4 5 1 0
1 0
5 3 0
3 0
样例输出 #1
2 4 5 3 1
代码
#include <stdio.h>
#include <stdlib.h>
void enqueue(int x); // 入队函数
int dequeue(); // 出队函数
void topo_sort(); // 拓扑排序函数
#define MAXN 1000
int N, G[MAXN][MAXN]; // 邻接矩阵表示的图
int indegree[MAXN]; // 入度数组
int Q[MAXN]; // 队列相关变量
int head = 0, tail = 0;
int main(int argc, char *argv[])
{
int i, v;
scanf("%d", &N);
for (i = 1; i <= N; i++)
{
while (scanf("%d", &v) && v != 0)
{
G[i][v] = 1; // 存在一条从i到v的边,v是i的后代
indegree[v]++; // v的入度加一
}
}
topo_sort();
return 0;
}
void enqueue(int x) // 入队函数
{
Q[tail++] = x;
}
int dequeue() // 出队函数
{
return Q[head++];
}
void topo_sort() // 拓扑排序函数
{
int i, u, v;
for (i = 1; i <= N; i++)
{
if (indegree[i] == 0)
{
enqueue(i); // 将入度为0的人加入队列
}
}
while (head != tail) // 队列不为空
{
u = dequeue(); // 从队列中取出(入度为0,即为祖先)
printf("%d ", u);
for (v = 1; v <= N; v++)
{
if (G[u][v] == 1)
{
indegree[v]--;
if (indegree[v] == 0)
{
enqueue(v);
}
}
}
}
}
到了这里,关于C语言-算法-拓扑排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!