一道特别考验语言功底的题目，首先它的输入与输出，对于我这种没有处理过复杂的输入，以及输出的渣渣来说，浪费了大量的时间，好在现在还稍微来得及，不怕不怕啦。紧接着，整个题目的要求也是比较复杂的，首先允许存在重复的数字对，也就是说，在输入的过程中，需要去重。若重复，则忽略。（具体实现过程中，使用一个edges的map表来去重的。）其次，顺序不唯一，同样的输入，打乱顺序后，会导致不同的输出。比如样例1与样例3。
结合题意，且对于树这种结构，首先需要确定根节点（那个没有父节点的），其次从根节点开始能够保证遍历所有的节点，且仅仅遍历一次。这就是这道题目解题的思路。而且，看题目中的要求，数字大小为1~2^31,所以这里不能够使用数组了，所以可以使用map来存储，首先需要一个邻接表的存储方式来存储读入的数据，其次需要一个字段来判断节点是否有父节点，为了便于实现对应不同的输入顺序有不同的输出过程，需要增加一个时间戳标记位timestamp和深度标记位dist来表示距离根节点的距离。
紧接着就是bfs的过程了，bfs过程必然用到队列的，所以整个过程代码实现如下：
import java.util.*;
import java.io.*;
public class Main{/** 以邻接表的形式存储整个树。 */static HashMap<Integer,ArrayList<Integer>> hh =new HashMap<>();/** 存下每个点的时间戳，用于确认bfs遍历的顺序 */static HashMap<Integer,Integer>timestamp=new HashMap<>();/** 节点到根节点的距离。 */static HashMap<Integer,Integer>dist=new HashMap<>();static HashMap<Integer,Boolean>has_father=new HashMap<>();static HashMap<Edges,Boolean>edges=new HashMap<>();public static void main(String[] args) throws IOException {Scanner sc=new Scanner(System.in);BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));int n=sc.nextInt();while (n!=0){n--;String str[]=sc.next().split(",");int a=Integer.parseInt(str[0]);int b=Integer.parseInt(str[1]);/* 存储时间戳记录的次序 */int tm=0;Edges edge=new Edges(a,b);if (edges.containsKey(edge)){continue;//用来除去序列中重复的边。}else{edges.put(edge,true);}if (!timestamp.containsKey(a)){timestamp.put(a,tm++);}if (!timestamp.containsKey(b)){timestamp.put(b,tm++);}has_father.put(b,true);if (!hh.containsKey(a)){ArrayList<Integer>list=new ArrayList<>();list.add(b);hh.put(a,list);}else{hh.get(a).add(b);}}String result=process(n);System.out.println(result);}private static String process(int n) {String result="";int root=-1;for (Integer p: hh.keySet()){if (has_father.get(p)==null){root=p;break;}}if (root==-1){return "Not a tree";}else{ArrayList<Integer>res=bfs(root);/* 进行宽度优先遍历 */if (res.size()<timestamp.size()){/* 如果整个树是不连通的，则判定不是一棵树 */return "Not a tree";}else{result+=res.get(0)+"";for (int i=1;i<res.size();i++){result+=","+res.get(i);}}}return result;}private static ArrayList<Integer> bfs(int root) {Queue<Integer>q=new LinkedList<>();q.offer(root);ArrayList<Integer>nodes = new ArrayList<>();dist.put(root,0);while(!q.isEmpty()){int t=q.poll();nodes.add(t);ArrayList<Integer>tem=hh.get(t);if (tem==null){continue;}for (Integer temp: tem){/* 当前节点已经被遍历过，说明在序列中该节点存在多个父节点 */if (dist.containsKey(temp)){return new ArrayList<>();}dist.put(temp,dist.get(t)+1);q.offer(temp);}}/*双关键字排序*/ArrayList<ArrayList<Integer>>ans=new ArrayList<>();for (Integer ver:nodes){ArrayList<Integer>list=new ArrayList<Integer>();list.add(dist.get(ver));list.add(timestamp.get(ver));list.add(ver);ans.add(list);}nodes.clear();Collections.sort(ans, new Comparator<ArrayList<Integer>>() {@Overridepublic int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {if (Objects.equals(o1.get(0), o2.get(0))){return o1.get(1)-o2.get(1);}return o1.get(0)-o2.get(0);}});for (ArrayList<Integer>t:ans){nodes.add(t.get(2));}return nodes;}}
class Edges{int first;int second;public Edges(int first,int second){this.first=first;this.second=second;}
}