题意分析

本题围绕火星人的复杂血缘关系及行星议会的发言顺序问题展开。

火星人的血缘关系混乱，他们可随意在任何时候、任何地方繁衍，一个火星人可能有一个或十个父母，也可能有上百个孩子，这对他们来说是自然的生活方式。

在行星议会中，这种混乱的族谱体系带来了尴尬。议会中有最杰出的火星人，为避免冒犯他人，发言顺序是先让年长的火星人发言，然后是较年轻的，最后是最年轻的无子女的评估员。但维持这个顺序并非易事，因为火星人不一定清楚自己所有的父母（更不用说祖父母了），若孙子先发言，随后是看起来年轻的曾祖父发言，就会引发丑闻。

题目要求编写程序，确定一个能保证议会中每个成员都比其后代先发言的顺序。

输入方面，第一行是一个自然数 (N)（(1≤ N≤100)），表示火星人行星议会成员的数量，成员按1到 (N) 编号。接下来 (N) 行，第 (i) 行包含第 (i) 个成员的子女列表，子女编号以任意顺序排列并用空格分隔，列表可能为空，且无论是否为空都以 (0) 结尾。

输出为一行，是满足条件的发言者编号序列（用空格分隔），若有多个序列满足条件，输出任意一个即可，且至少存在一个这样的序列。例如输入数据1，输出“2 4 5 3 1” 就是满足条件的一种发言顺序。

题意分析

1. 背景设定：火星人的血缘关系极为复杂，繁衍方式独特，导致每个火星人的父母和子女数量不固定，这种复杂的血缘关系在火星行星议会中引发了问题。

2. 议会发言规则：在行星议会中，为避免冒犯他人，发言顺序遵循特定规则，即先让年长的火星人发言，再是较年轻的，最后是最年轻且无子女的议员。由于火星人并不总是清楚自己所有的父母及祖辈，确定一个能保证每个议员都比其后代先发言的顺序变得至关重要。

3. 输入信息：输入的第一行给出一个整数$N$（$1 \leq N \leq 100$ ），代表火星行星议会成员的数量。后续有$N$行，其中第$i$行表示编号为$i$的火星人议员的子女列表。列表中的数字是其子女的编号，以任意顺序排列，用空格分隔，列表以$0$结尾，列表可能为空。这意味着输入通过这种方式描述了火星人之间的血缘关系，即有向图中的边（从父母节点指向子女节点）。

4. 输出要求：需要输出一个由议员编号组成的序列，编号之间用空格隔开。这个序列要满足在议会发言顺序中，每个议员都在其后代之前发言。如果存在多个满足条件的序列，输出任意一个即可，并且题目保证至少存在一个这样的序列。

解题思路：

首先，根据输入构建有向图。每个火星人是图中的一个节点，若火星人A是火星人B的父母，则从A节点到B节点存在一条有向边。同时，记录每个节点（火星人）的入度（即其父母的数量），入度为0的节点表示没有父母的火星人（在血缘关系中处于最顶端）。

然后，进行拓扑排序。从入度为0的节点开始选择，将其输出作为发言顺序的一部分，并将该节点的所有出边（指向其子女的边）删除，这会导致其子女节点的入度减1。不断重复这个过程，直到所有节点都被处理完毕。由于题目要求每个成员都比其后代先发言，拓扑排序的结果恰好满足这一条件，因为拓扑排序的本质就是按照有向图中节点的先后顺序（无前驱节点的先输出）进行排序。

分析

1.时间复杂度：在构建图时，对于每个节点（共 N 个），需要处理其子女列表，最坏情况下每个节点的子女列表长度为 N，所以构建图的时间复杂度为O(N2)。在拓扑排序过程中，每次选择入度为 0 的节点并更新其邻接节点的入度，每个节点和每条边最多被处理一次，时间复杂度为O(N + M)，其中 M 是边的数量。在本题中，M 最大为N2，所以整体时间复杂度为O(N2)。

2.空间复杂度：使用邻接表存储图结构，需要存储 N 个链表头指针和 M 个边节点，空间复杂度为O(N + M)。同时，还使用了一个数组 sum 来记录每个节点的入度，大小为 N。因此，总的空间复杂度为O(N + M)，在最坏情况下为O(N2)。

实现步骤

1.输入处理：读取议会成员数量 N。对于每个成员 i（1 ≤ i ≤N ），读取其子女列表。在读取过程中，构建邻接表表示的有向图，同时更新每个子女节点的入度。

2.拓扑排序初始化：遍历所有节点，找到入度为 0 的节点，作为拓扑排序的起始点。

3.拓扑排序过程：找到一个入度为 0 的节点 j，输出该节点编号，表示该火星人先发言。将该节点的入度设为一个很大的值（如1<<30），标记其已被处理。遍历该节点的所有邻接节点（即其子女节点），将这些子女节点的入度减 1，表示删除从该节点到其子女节点的边。重复上述步骤，直到所有节点都被处理完毕。

C++ 实现

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct edge{
	int v;
	edge *next;
}*head[105];
int sum[105];
edge *make(){
	return (edge *)(malloc(sizeof(edge)));
}
void add(int u,int v){
	edge *x=make();
	x->v=v;
	x->next=head[u];
	head[u]=x;
}
int main(){
	int n,i,x,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		while(x){
			add(i,x);
			sum[x]++;
			scanf("%d",&x);
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(!sum[j]){
				break;
			}
		}
		printf("%d ",j);
		sum[j]=1<<30;
		edge *now=head[j];
		while(now){
			sum[now->v]--;
			now=now->next;
		}
	}
	return 0;
}

代码说明：

1.头文件包含： #include <stdio.h>、#include <stdlib.h>和#include 分别引入了标准输入输出库、标准库和输入输出流库，用于输入输出操作。using namespace std;使代码可以直接使用标准命名空间中的函数和类型。

2.结构体定义： struct edge{int v; edge *next; }*head[105];定义了一个链表节点结构体 edge，用于构建邻接表表示有向图。head 数组用于存储每个节点的链表头指针，大小为 105（略大于题目中 N 的最大可能值 100，防止数组越界）。int sum[105];定义了一个数组 sum，用于记录每个节点的入度。

3.函数定义：

（1）edge *make()：用于创建一个新的链表节点，分配内存并返回指向该节点的指针。

（2）void add(int u, int v)：用于向有向图中添加一条从节点 u 到节点 v 的边。创建一个新节点并插入到 u 节点的邻接链表头部。

4.主函数： 读取议会成员数量 N。通过两层循环读取每个成员的子女列表，调用 add 函数构建有向图，并更新子女节点的入度。进行拓扑排序。外层循环控制处理的节点数量，内层循环找到一个入度为 0 的节点 j。输出 j 后，将其入度设为很大的值，遍历其邻接节点并将邻接节点的入度减 1。程序结束时返回 0。