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

家谱树"/>

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

【模板】拓扑排序 / 家谱树

题目描述

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

输入格式

第 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 表示描述完毕。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

2 4 5 3 1

code

#include<bits/stdc++.h>
using namespace std;
#define i64 long long 
#define FOR(i,n,s) for(int i=(s);i<=(n);i++)
const i64 MAXN=1e5;
const i64 INF=LLONG_MAX; 
i64 t,topo[MAXN],vis[MAXN],n;
vector<i64> G[MAXN];
bool dfs(int u)
{vis[u]=-1;for(auto &v:G[u]){if(vis[v]==-1) return false;if(!vis[v]&&!dfs(v)) return false;}vis[u]=1;topo[t--]=u;return true;
}
bool toposort()
{t=n;memset(vis,0,sizeof(vis));FOR(u,n,1) if(!vis[u])if(!dfs(u)) return false;return true;
}
void init()
{cin>>n;FOR(i,n,1){int x;while(cin>>x&&x!=0)	G[i].push_back(x);} 
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);init();toposort();for(int i=1;i<=n;i++)cout<<topo[i]<<" ";return 0;
} 

ps:

拓扑排序的步骤：
计算每个点的入度。入度为0就加入队列。当队列不为空则循环：取出队首元素并输出。遍历队首元素的连边，对应节点的入度 -1。当对应的节点入度为 0 就加入队列。