首页 > 试题广场 >

紧急疏散

[编程题]紧急疏散

热度指数：2273 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围： $1 \le n \le 10^5 \$

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

Python

sky游荡

BFS

from collections import defaultdict
tree = defaultdict(list)
n = int(input())
for _ in range(n-1):
    x,y = map(int,input().split())
    tree[x].append(y)
    tree[y].append(x)
def bfs(node,tree):
    c = 1
    queue = [node]
    visited = set()
    visited.add(1)
    visited.add(node)
    while queue:
        tmp = queue.pop(0)
        for d in tree[tmp]:
            if d not in visited:
                c+=1
                queue.append(d)
                visited.add(d)
    return c 
max_value = 0
for node in tree[1]:
    max_value = max(bfs(node,tree),max_value)
print(max_value)

发表于 2020-04-22 22:25:39 回复(0)

Python

汤普森30

# 为啥只能过80%呢 
N = int(input())
graph = [set() for _ in range(N+1)]
for i in range(N-1):
    a, b= list(map(int, input().split()))
    graph[a].add(b)
    graph[b].add(a)

def dfs(index):
    if len(graph[index])==0:
        return 1
    count = 1
    while len(graph[index]) > 0:
        ind = graph[index].pop()
        graph[ind].remove(index)
        count += dfs(ind)
    return count
res = -1
while len(graph[1]) > 0:
    ind = graph[1].pop()
    graph[ind].remove(1)
    res = max(res, dfs(ind))
print(res)

发表于 2019-08-23 11:40:32 回复(1)