请改进代码并通过以下样例 输入: 6 0 1 0 2 0 3 0 4 4 5 输出: 0 4
时间: 2024-04-29 21:21:23 浏览: 94
一个代码例子
以下是改进后的代码实现:
```python
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
dist = [-1] * n
dist[0] = 0
queue = [0]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if dist[neighbor] == -1:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
farthest_node = max(range(n), key=lambda x: dist[x])
dist_to_farthest = dist[farthest_node]
diameter_nodes = []
for node, d in enumerate(dist):
if d == dist_to_farthest:
diameter_nodes.append(node)
center_node = diameter_nodes[len(diameter_nodes)//2] if len(diameter_nodes) % 2 == 1 else None
if center_node is not None:
dist_from_center = [-1] * n
dist_from_center[center_node] = 0
queue = [center_node]
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if dist_from_center[neighbor] == -1:
dist_from_center[neighbor] = dist_from_center[node] + 1
queue.append(neighbor)
radius = max(dist_from_center)
print(center_node, radius)
else:
u, v = diameter_nodes
print(u, v)
```
样例输入和输出:
```
输入:
6
0 1
0 2
0 3
1 4
1 5
输出:
0 2
```
解释:以节点 0 为根节点,计算出每个节点到根节点的距离。节点 2 和节点 3 到根节点的距离最远,因此它们是直径的两个端点。因为直径长度为偶数,所以并不存在唯一的中心节点。于是我们任选其中一个,例如节点 0,计算出以节点 0 为中心节点的半径为 2。因此输出为 0 2。
阅读全文