题目描述
火星人的血缘系统已经够混乱了。实际上，火星人会在他们想要的时间和地点发芽。他们聚集在不同的群体中，所以一个火星人可以有一个父母也可以有十个。没有人会对一百个孩子感到惊讶。火星人已经习惯了这一点，他们的生活方式在他们看来很自然。
在行星委员会中，混乱的系谱系统导致了一些尴尬。在那里会见最有价值的火星人，因此为了在所有讨论中不冒犯任何人，它首先被用来让年长的火星人发言，而不是年轻的火星人，仅是最年轻的没有孩子的评估员。不过，维持这个秩序还真不是一件小事。 Martian 并不总是认识他所有的父母（而且他的祖父母没有什么可说的！）。但是，如果错误地先说一个孙子，而只说他年轻的曾祖父，这就是真正的丑闻。
您的任务是编写一个程序，该程序将一劳永逸地定义一个顺序，以保证理事会的每个成员都比其后代更早发言。
输入
标准输入的第一行只包含一个数字 N, 1 <= N <= 100 — 火星行星委员会成员的数量。根据数百年的传统，理事会成员是用从 1 到 N 的自然数来枚举的。此外，正好有 N 行，而且，第 I 行包含了第 I 名成员的孩子的列表。子项列表是由空格分隔的任意顺序的子项序列号序列。子项列表可能为空。该列表（即使它是空的）以 0 结尾。
输出
标准输出应该在其唯一的一行中包含一个由空格分隔的说话者号码序列。如果有几个序列满足问题的条件，则将其中的任何一个写入标准输出。至少一个这样的序列总是存在。
输入样例:
5 0 4 5 1 0 1 0 5 3 0 3 0
输出样例:
2 4 5 3 1
题目含义:在说话时,长辈必须要比晚辈先说.输入的N行中,第i行是该行的孩子列表(u1,u2…),相当于有一条i - > u的边(在拓扑序列中->表示,方向与顺序表示前面的序号排在后面之前).题目的意思是求拓扑序列,并且该序列还是一直存在的.
关于拓扑序列的思路:
想让入度为0的点入栈.
依次从栈中弹出节点,删除该点的所有边(也就是出度边,对应着操作就是所有邻接点的入度-1).如果该点的临界点入度-1之后的入度为0,则进栈.
持续进行2操作,直至栈为空为止
AC代码
#include<iostream> #include<stack> using namespace std; const int maxn = 110; int map[maxn][maxn],indegree[maxn],topo[maxn],n; stack<int> s; void TopoSort() { int cnt = 0; for(int i = 1; i <= n; i++) { if(!indegree[i]) { s.push(i); } } while(!s.empty()) { int u = s.top(); s.pop(); topo[cnt++] = u;//将入度为0的点加入topo序列. for(int i = 1; i <= n; i++) { //让u的所有临界点,入度-1 if(map[u][i]) { indegree[i]--; if(!indegree[i]) { //如果入度为0则入栈. s.push(i); } } // if(!indegree[i]){//如果入度为0则入栈. 这个if条件一定要写在上面 ,只有是u的临界点了才进行入度-1并 进行判断入度是否为0. // s.push(i); // } } } } int main() { cin>>n; int v; for(int i = 1; i <= n; i++) { while(cin>>v&&v) { map[i][v] = 1; indegree[v]++; } } TopoSort(); for(int i = 0; i < n-1; i++) { cout<<topo[i]<<" "; } cout<<topo[n-1]<<endl; return 0; }
