参考文献

参考闫神的视频转换成了java代码 供参考
对我来说反正是挺难的题了

输入

5
1,2
1,3
2,4
2,5
3,6

输出

1,2,3,4,5,6

对应的树结构为

1

/ \
2 3
/ \ /
4 5 6

JAVA代码

import java.util.*;

public class Main {
    static Map<Integer, List<Integer>> h = new HashMap<>(); //存储整个图 key为起点的所有边
    static Map<Integer,Integer> timeStamp = new HashMap<>(); //存储每个点的时间戳，即同一层 谁先存，谁后存
    static Map<Integer,Integer> dist = new HashMap<>(); //存储每个节点与根节点的层数距离 如 根节点本身与根节点的层数相差为0，根节点的子节点如案例中的 根节点为1，那么子节点2与1的距离就为1
    static Map<Integer,Boolean> hasFather = new HashMap<>();  //存储每个节点是否有父节点 每个节点只能有一个父节点， 没有父节点的节点即为根节点
    static Map<Pair,Boolean> isSaved = new HashMap<>();   //存储某个线段是否被用过了，用过即跳过
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int tm=0;
        for (int i = 0; i < n; i++) {
            String input = sc.next();
            String[] inputs = input.split(",");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            Pair p = new Pair(a,b);
            if (isSaved.containsKey(p)) continue; //如果已经存储过了 那么就直接跳过
            isSaved.put(p,true);
            if (!timeStamp.containsKey(a)) timeStamp.put(a,tm++);  //存储节点的时间戳
            if (!timeStamp.containsKey(b)) timeStamp.put(b,tm++); //存储节点的时间戳
            if (!h.containsKey(a)){  //存储一条边
                List<Integer> tempList = new ArrayList<>(); 
                tempList.add(b);
                h.put(a,tempList);
            }else {
                h.get(a).add(b);
            }
            hasFather.put(b,true);  //保存当前节点b是有父节点的
        }
        int root = -1;
        for (Map.Entry<Integer, Integer> entry : timeStamp.entrySet()) {  //对时间戳进行遍历找到根节点
            int p = entry.getKey();
            if (!hasFather.containsKey(p)){
                root=p;
                break;
            }
        }

        if (root==-1) {   //如果找不到根节点
            System.out.println("Not a tree");
        }
        else {  //如果找到根节点 就对根节点进行宽搜

            List<Integer> res =bfs(root);
            if (res.size()<timeStamp.size()) System.out.println("Not a tree");
            else {
                System.out.print(res.get(0));
                for (int i = 1; i < res.size(); i++) {
                    System.out.print(","+res.get(i));
                }
            }
        }

    }

    private static List<Integer> bfs(int root) {
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(root);
        dist.put(root,0);
        List<Integer> nodes = new ArrayList<>();
        while (!queue.isEmpty()){
            Integer t = queue.poll();
            nodes.add(t);
            List<Integer> tempList = h.get(t);
            if (tempList==null) continue;
            for (Integer ver : tempList) {
                if (dist.containsKey(ver)) return new ArrayList<>();
                dist.put(ver,dist.get(t)+1);
                queue.offer(ver);
            }
        }
        List<Node> ans = new ArrayList<>();
        for (Integer ver : nodes) {
            ans.add(new Node(dist.get(ver),timeStamp.get(ver),ver));
        }
        Collections.sort(ans);
        nodes.clear();
        for (Node t : ans) {
            nodes.add(t.ver);
        }
        return nodes;
    }
}
class Node implements Comparable<Node>{
    int dist;
    int timeStamp;
    int ver;

    public Node(int dist, int timeStamp, int ver) {
        this.dist = dist;
        this.timeStamp = timeStamp;
        this.ver = ver;
    }


    @Override
    public int compareTo(Node o) {
        if (o.dist!=this.dist){
            return this.dist-o.dist;
        }else{
            return this.timeStamp-o.timeStamp;
        }
    }
}

class Pair{
    int a;
    int b;

    public Pair(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return a == pair.a &&
                b == pair.b;
    }

    @Override
    public int hashCode() {
        return Objects.hash(a, b);
    }
}