Genealogical tree
描述
火星人的血缘关系系统已经够混乱的了。实际上，火星人想在什么时候，什么地方发芽。
他们以不同的群体聚集在一起，这样一个火星人可以有1个父母，也可以有10个父母。
没有人会对100个孩子感到惊讶。火星人已经习惯了这一点，他们的生活方式似乎很自然。
在行星理事会中，混乱的家谱系统导致了一些尴尬。在那里会遇到最有价值的火星人，因此为了在所有的讨论中不冒犯任何人，它首先被用来给老火星人发言，
而不是给年轻火星人发言，并且只给最年轻的没有孩子的评估员发言。
然而，维护这一秩序确实不是一件小事。火星人并不总是认识他所有的父母（关于他的祖父母也没什么好说的！）。
但如果一个孙子第一次说错了，而且只比他年轻貌似曾祖父，这真是个丑闻。
你的任务是写一个程序，这个程序将一劳永逸地确定一个命令，保证委员会的每一个成员都比他的每一个后代更早发言。
Input
标准输入的第一行只包含一个数字N，1<=N<=100 --火星行星理事会的成员数。
根据几百年的传统，理事会成员是以从1到N的自然数来计算的。
此外，正好有N行，而且，第I行包含第I个成员的孩子的列表。
孩子列表是由孩子序列号组成的序列，按任意顺序用空格隔开。
孩子列表列表可能为空。列表（即使是空的）以0结尾。
Output
标准输出应该是：包含一个发言者编号的唯一行的序列，用空格隔开。
如果有几个序列满足问题的条件，则要将其中任何一个序列写入标准输出。
至少存在一个这样的序列。
Sample Input
5
0
4 5 1 0
1 0
5 3 0
3 0
Sample Output
2 4 5 3 1
解决方案：有向图，提及入度，出度，且需要排序，故使用拓扑排序
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/**
*
* @author XA-GDD
**解决方案：有向图，提及入度，出度，且需要排序，故使用拓扑排序
*/
public class G_GenealogicalTree{
static int N;
static MartianNode [] martianEdgeArr ;
static ArrayList<Integer> orderList = new ArrayList<Integer>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while (br.ready()) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
martianEdgeArr = new MartianNode[N+2];
for(int i=1;i<=N;i++) {
martianEdgeArr[i] = new MartianNode(i,i);
}
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine());
while(true) {
int childNumb = Integer.parseInt(st.nextToken());
if(childNumb==0) {
break;
}
martianEdgeArr[i].children.add(childNumb);
martianEdgeArr[i].outDegree += 1;
martianEdgeArr[childNumb].inDegree +=1;
}
}
topologicalOrder();
for(int i=0;i<orderList.size();i++) {
System.out.print(orderList.get(i)+" ");
}
System.out.println();
}
}
static void topologicalOrder() {
Queue<Integer> queue = new LinkedList<Integer>();
for(int i=1;i<=N;i++) {
if(martianEdgeArr[i].inDegree==0) {
martianEdgeArr[i].valSum = martianEdgeArr[i].val;
queue.add(i);
}
}
while(!queue.isEmpty()) {
int curr = queue.poll();
orderList.add(curr);
for(int i=0;i<martianEdgeArr[curr].children.size();i++) {
int next = martianEdgeArr[curr].children.get(i);
if(martianEdgeArr[next].inDegree==0) {
continue;
}
martianEdgeArr[next].inDegree -= 1;
martianEdgeArr[next].valSum = Math.max(martianEdgeArr[next].valSum, martianEdgeArr[curr].valSum+martianEdgeArr[next].val);
if(martianEdgeArr[next].inDegree==0) {
queue.add(next);
}
}
}
}
}
class MartianNode{
int index;
int val;
int inDegree;
int outDegree;
int valSum;
ArrayList<Integer> children;
MartianNode(int index, int val){
this.index = index;
this.val = val;
this.inDegree = 0;
this.outDegree = 0;
this.valSum = Integer.MIN_VALUE;
this.children = new ArrayList<Integer>();
}
}