1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
# 3203. Find Minimum Diameter After Merging Two Trees
"""
there exists two undirected trees with 'n' and 'm' nodes numbered from 0 to
'n - 1' and from 0 to 'm - 1', respectively. you are given two 2d integer
arrays 'edges1', and 'edges2' of lengths 'n - 1' and 'm - 1', respectively,
where 'edges1[i] = [a_i, b_i]' indicates that thereis an edge between nodes
'a_i' and 'b_i' in the first tree, and 'edges2[i] = [u_i, v_i]' indicates
there is an edge between nodes 'u_i' and 'v_i' in the second tree. you must
connect one node from the first tree with another node from the second tree
with an edge. return the minimum possible diameter of the resulting tree. the
diameter of a tree is the length of the longest path between any two nodes in
the tree
"""
class Solution(object):
def minimumDiameterAfterMerge(self, edges1, edges2):
"""
:type edges1: List[List[int]]
:type edges2: List[List[int]]
:rtype: int
"""
def farthest(hash, i):
n = len(hash)
bfs = [i]
vis = [0] * n
vis[i] = 1
res, diam = -1, -1
for i in bfs:
for j in hash[i]:
if vis[j] == 0:
vis[j] = vis[i] + 1
bfs.append(j)
if vis[j] > diam:
res = j
diam = vis[j]
return res, diam - 1
def diameter(edges):
if not edges:
return 0, 0, 0
n = len(edges) + 1
hash = [[] for i in range(n)]
for i, j in edges:
hash[i].append(j)
hash[j].append(i)
v1, d = farthest(hash, 0)
v2, d = farthest(hash, v1)
return d, v1, v2
d1, i, j = diameter(edges1)
d2, i, j = diameter(edges2)
return max(d1, d2, (d1 + 1) // 2 + (d2 + 1) // 2 + 1)
if __name__ == "__main__":
obj = Solution()
print(
obj.minimumDiameterAfterMerge(edges1=[[0, 1], [0, 2], [0, 3]], edges2=[[0, 1]])
)
print(
obj.minimumDiameterAfterMerge(
edges1=[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 6], [2, 7]],
edges2=[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 6], [2, 7]],
)
)
|