家谱树"/>
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 就加入队列。
更多推荐
B3644 【模板】拓扑排序 / 家谱树
发布评论