当前位置: 首页 > >

美团笔试

发布时间:

给定一张包含N个点、N-1条边的无向连通图,节点从1到N编号,每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点,那么总路程至少是多少?


输入描述:


第一行包含一个整数N,1≤N≤10^5。

接下来N-1行,每行包含两个整数X和Y,表示X号节点和Y号节点之间有一条边,1≤X,Y≤N。

输出描述:


输出总路程的最小值。

输入例子1:


4
1 2
1 3
3 4

输出例子1:


4

python代码:


n=int(input())
graph={}
for i in range(1,n+1):
? ? graph[i]=[]
for _ ?in range(n-1):
? ? f=[int(x) for x in input().split()]
? ? graph[f[0]].append(f[1])
? ? graph[f[1]].append(f[0])
def dfs(x,old,w):
? ? global ans
? ? for i in range(len(graph[x])):
? ? ? ? if (graph[x][i]==old):
? ? ? ? ? ? continue
? ? ? ? dfs(graph[x][i],x,w+1)
? ? ans=max(ans,w)
? ? return ans
ans=0
m=dfs(1,-1,0)
print((n-1)*2-m)

思路:首先,这个图可以看成一个树,它是一个没有环的,就是将从1出发的所有路径都遍历一遍,寻找一条最长的,让它只走一遍,这样我们得到的答案就是最小的。牛客的通过率是66.7%,报数组越界错误。



友情链接: