登录
  • #刷题

难题‌‌‍‍‌‍‌‌‌‌‍‍‌‍‌‍‍‌‍‍‌‌‌‌‍‍‍‌‍‍‌‍"Count Subtrees With Max Distance Between Cities"结果不对

ATPtennis
149
4
EXAMPLE 1的结果是[3, 4, 0],我这个代码运行完了是[0, 1, 0]。这题真是相当强悍了,融合了找全部子数组,subsets这题,和tree diameter找最大边数两大知识点,我代码也是按照这思路写的,可是不知道为什么运行结果错误,妄解惑!谢谢!

from collections import defaultdictclass Solution:

def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:

def dfs(root, prev):

d1 = d2 = 0

for nex in graph[root]:

if nex != prev and nex in subtree:

d = dfs(nex, root)

if d > d1:

d1, d2 = d, d1

elif d > d2:

d2 = d

self.max = max(self.max, d1+d2)

return d1 + 1

# build graph

graph = defaultdict(set)

for i, j in edges:

graph.add(j)

graph[j].add(i)

# Get all subtrees

for i in range(1 << n):

subtree = [][br]
for j in range(n):

if i & 1 << j:

subtree.append(j+1)

# we have got a subtree, then we need to verify if it is valid

number = 0

for p, q in edges:

if p in subtree and q in subtree:

number += 1

if number < 1 or len(subtree) != number + 1:

continue

# we get the valid tree. we need to get the maximal diameter

self.max = 0

result = [0 for i in range(n-1)]

dfs(subtree[0], None)

result[self.max - 1] += 1

return result

补充内容 (2021-09-15 16:04 +8:00):

找到了问题所在,把result = [0 for i in range(n-1)] 这行移出for循环,写到外面即可。

这道题是一道大综合,考察了树如何找最大直径,还有如何找一个数组的所有集合。然后判断这个集合是否是你想要的。综合起来去解决这道问题即可。
4条回复
热度排序

发表回复