寒假集训10——图论2

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

#include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; int n; vector <int> g[110]; vector <int> in(110, 0);//入度 queue <int> q; vector <int> ans; int main() { cin >> n; //建图 for (int i = 1;i <= n;i++) { int x = 1; while (x != 0) { cin >> x; if (x != 0) { g[i].push_back(x); in[x]++; } } } //把入度为0的点加入队列 for (int i = 1;i <= n;i++) { if (in[i] == 0) q.push(i); } while (!q.empty()) { int t = q.front(); ans.push_back(t); q.pop(); for (int e : g[t]) { in[e]--;//消除e的入度影响 //把入度为0的点加入队列 if (in[e] == 0) q.push(e); } } for (int e : ans) cout << e << " "; return 0; }