紧急疏散(python)

题目描述：

体育场突然着火了，现场需要紧急疏散，但是过道真的是太窄了，同时只能容许一个人通过。现在知道了体育场的所有座位分布，座位分布图是一棵树，已知每个座位上都坐了一个人，安全出口在树的根部，也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点，但是除了安全出口以外，没有任何一个结点可以同时容纳两个及以上的人，这就需要一种策略，来使得人群尽快疏散，问在采取最优策略的情况下，体育场最快可以在多长sh时间内疏散完成。（2019京东算法实习招聘）

 输入：

第一行包括一个整数n，即树的结点数量(1<=n<=100000)

接下来有n-1行，每行有两个正整数x，y，表示在x和y结点之间存在一条边。(1<=x<=y<=n)

输出：

输出仅包含一个正整数，表示所需要的最短时间

样例输入：

6

2 1

3 2

4 3

5 2

6 1

样例输出：

4

#定义一个列表，存放和1直接相连接的值，不直接相连的先放到一个临时列表中，一层一层过滤
import sys

#all_list用于存放直接和1相连的数据，比如2、4和1直接相连，则all_list为[[2],[4]]
#temp用于存放不和1直接相连的数据组，比如[2,3],[4,5]不和1直接相连，则temp为[[2,3],[4,5]]
all_list = list()
temp = list()

#先取出第一行的值，然而后面并没有用到
num = int(sys.stdin.readline().strip())

line = sys.stdin.readline().strip()
while len(line):
    two = list(map(int,line.split(' ')))
    #两个有其中一个是1，将另一个作为列表放入all_list中，否则一组数都放到temp中去
    if two[0] == 1 or two[1] == 1:
        #判断两个哪个不是1
        if two[0] == 1:
            all_list.append([two[1]])
        else:
            all_list.append([two[0]])
    else:
        temp.append(two)
    line = sys.stdin.readline().strip()
    
#所有数据都遍历过一遍，并且所有和1连接的值都以list的格式放入到all_list中
index_ = list()
while len(temp) != 0:
    #遍历一遍temp列表，看里面有没有和all_list中相连接的
    for i in range(len(temp)):
        #每一个temp中的值都要和all_list中的每一个值进行配对
        for j in range(len(all_list)):
            #两个其中在all_list中，将另一个放入
            if temp[i][0] in all_list[j] or temp[i][1] in all_list[j]:
                if temp[i][0] in all_list[j]:
                    all_list[j].append(temp[i][1])
                else:
                    all_list[j].append(temp[i][0])
                index_.append(temp[i])
    for i in range(len(index_)):
        temp.remove(index_[i])
                    
#判断all_list中最长的那个列表的长度
max_len = 0
for i in range(len(all_list)):
    len_ = len(all_list[i])
    if len_ > max_len:
        max_len = len_
        
print(max_len)

菜鸟一枚，代码仅供参考，如有问题，望指正~