Python 代码

#没有默认的输入顺序，第一行可能不是根节点，最后一行可能不是叶子节点，所以要先找根节点

#可能有完全重复的行, 判断NOT a tree时，不能简单判断son中有重复结点，还要判断这些重复结点的父结点是否也一样

#A tree:
#必须有一个根节点（没有父结点的点）；
#可以从根节点遍历到其他所有结点（这一点包含了有多个根节点的情况）；
#除了根节点的其他点都只有一个父结点（每个点只被遍历一次）；

import collections #容器数据类型包
from queue import Queue

#全局变量
has_father = dict() #每个点是否有父结点
time_stamp = collections.OrderedDict() #记录时间戳
dist_to_root = collections.OrderedDict() #记录每个点到根节点的距离
tree = dict() #记录整幅图，元素为(key=father,value=[son1,son2,...])
edges = []

def bfs(root):
    #通过队列遍历构造树，先求所有的dist
    q = Queue()
    q.put(root)
    dist_to_root[root]=0    
    while(q.qsize()>0):
        t = q._get()
        #print("t,tree[t]:",t)
        #print(tree[t])
        for ver in tree[t]:
            if ver in dist_to_root.keys(): #说明t被重复遍历过，t不只有一个父结点
                print("Not a tree")
                return []
            dist_to_root[ver]=dist_to_root[t]+1 #结点dist等于其父结点dist+1
            if ver in tree.keys():
                q.put(ver)

    node_list = []
    for node in dist_to_root.keys():
        node_list.append([node,dist_to_root[node],time_stamp[node]])
    sorted_node = sorted(node_list,key=lambda x:(x[1],x[2]))

    res=[]
    for i in range(len(sorted_node)):
        res.append(sorted_node[i][0])
    return res


def main():
    tm = 0 #时间戳从0开始
    #读入数据
    line = input()
    N = int(line)
    father = [0]*N
    son = [0]*N
    for i in range(N):
        line = input()
        line = line.split(',')
        father = line[0]
        son = line[1]

        #忽略重复输入的边
        if (father,son) in edges:
            continue
        edges.append((father,son))

        if father not in time_stamp.keys():
            time_stamp[father] = tm
            tm +=1
        if son not in time_stamp.keys():
            time_stamp[son] = tm
            tm += 1
        has_father[son]=True
        if father not in tree.keys():
            tree.setdefault(father,[])
        tree[father].append(son)
    #找根节点
    root = -1 #由于各节点值为正整数，所以根可以初始化为-1
    for key in time_stamp.keys():
        if key not in has_father.keys():
            #找到了一个根节点
            root = key
            break
    if root == -1: #没有根节点，所有点都有父结点
        print("Not a tree")
        return
    else:
        res = bfs(root) #宽度优先遍历输出节点list
        if len(res)==0:
            return
        if len(res)<len(time_stamp.keys()):
            print("Not a tree")
            return
        else:
            print(" ".join(str(i) for i in res))





if __name__ == "__main__":
    main()