某大厂一道笔试编程题

题目意思大概是一个体育场座位分布为树形结构，因为事故需要紧急撤离人群，安全出口在根节点处，假设除了根节点外所有节点均只能容纳一个人（根节点容纳人数不受限），且没每次只能移动一个节点，问至少需要多少次移动所有人才能全部撤离，输入数据的结构如下，其中第一行表示根节点的序号，其余各行表示所有存在边相连的节点，用空格隔开

0
0 1
0 5
0 6
1 2
2 3
2 4
6 7
6 9
6 8
7 10

算法分析：想象这个树形图的结构，由于根节点可容纳无数多人，所以每次移动所有位于第一子节点处的人都能移动到根节点，如果将所有第一子节点分别作为根节点考察它们对应的子树，则每一次移动都等效于对所有这些子树都减掉它们的一个叶结点，所以最少的移动次数应当是所有子树中最大的子节点数加上1

Python代码实现

def node_number(root,list):
    child=[]
    delete=[]
    for link in list:
        if root in link:
            delete.append(link)
            link.remove(root)
            child.append(link[0])
    if not delete:
        return 0
    for x in delete:
        list.remove(x)
    sum=len(child)
    for son in child:
        sum+=node_number(son,list)
    return sum

def input_tree():
    node=int(input())
    tree=[[0]]
    while True:
        a=input().split()
        if a:
            b = [int(x) for x in a]
            tree.append(b)
        else:
            break
    return node,tree[1:]

if __name__=='__main__':
    node,tree=input_tree()
    son=[]
    dele=[]
    for line in tree:
        if node in line:
            line.remove(node)
            son.append(line[0])
            dele.append(line)
    for x in dele:
        tree.remove(x)
    number=[]
    for s in son:
        number.append(node_number(s,tree))
    print(max(number)+1)

用题给的示例所得的运行结果为：

5