洛谷 B3644 【模板】拓扑排序 / 家谱树 C语言

题目：

https://www.luogu.com.cn/problem/B3644

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

2 4 5 3 1

思路：

拓扑排序可以利用dfs和bfs实现，我这里使用的是bfs

1.在输入的时候实现有向图和入度处理

2.bfs利用队列，将找到的入度为0的压入队首，在入度为0的节点寻找子节点，用一个循环遍历行，减去子节点的入度，为0的时候压入队列。

3.我们需要用一个vis状态数组来储存入度为0的节点，相当于删除节点

代码如下：

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct Node {
    int id = 0;
};
bool vis[5001];//记录点 
int n;
int G[5001][5001]; // 数组大小设为5001以允许索引0-5000，或保持5000但使用1-5000索引
Node num[5001];//结构体类型的数组，作为节点 
queue <int> q;

void check()//检查函数 
{
	    for (int i = 1; i <= n; i++) 
		{
        for (int j = 1; j <= n; j++) 
		{
            cout << G[i][j] << " ";
        }
        cout << endl;
    }
    for(int i = 1 ; i <= n ; i++) 
    {
    	cout << "节点: " << i << " id->" << num[i].id << endl;
	}
	cout << endl;

}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
	{
        int t;
        while (cin >> t && t != 0) 
		{
            G[i][t] = 1;
            num[t].id++;//入度

        }
    }
//	check();//检查
	for(int i = 1 ; i <= n ; i++)
	{
		if(num[i].id == 0)
		{
			q.push(i);
		}
	 } 
	while(!q.empty())
	{
		int head = q.front();
		q.pop();
		if(num[head].id == 0)
		cout << head << endl;
		 for (int k = 1; k <= n; k++) 
		 {
            if (G[head][k] == 1)// 遍历邻接节点并更新入度 
			{
                num[k].id--;//减去入度
                if (num[k].id == 0 && !vis[k]) 
				{
                    q.push(k);//入队
                    vis[k] = true;//标记已访问
                }
            }
         }
	}
    return 0;
}