Show problems as
Classic problem #3203HardTreeDepth-First SearchBreadth-First SearchGraph Theory

Find Minimum Diameter After Merging Two Trees

Real-world version: Bridging Two Footpath Networks
Tracked in this browser only
Read Find Minimum Diameter After Merging Two Trees on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A campus has two footpath networks that share no paths at all. The first network has n junctions labelled 0 to n - 1; the second has m junctions labelled 0 to m - 1, numbered independently of the first. Each network is given as an edge list: edges1 holds n - 1 pairs [a, b] meaning a two-way footpath joins junctions a and b of the first network, and edges2 holds m - 1 pairs describing the second network the same way. So n is edges1.length + 1 and m is edges2.length + 1, and a network of one junction arrives as an empty edge list. Within each network every junction is reachable from every other and there are no cycles.

The walk length between two junctions is the number of footpaths on the unique route between them, and the stretch of a network is the largest walk length over all pairs of its junctions. A network of one junction has stretch 0.

Facilities will build exactly one new two-way footbridge, from some junction of the first network to some junction of the second, leaving one combined network. They may pick any such pair of endpoints. Return the smallest stretch the combined network can have.

Examples

Example 1

Input
edges1 = [[0,1],[1,2],[2,3]], edges2 = [[1,0],[1,2],[3,1]]
Output
4

The first network is the chain 0-1-2-3, of stretch 3. The second has junction 1 joined to 0, 2 and 3, of stretch 2. Bridging junction 1 of the first network to junction 1 of the second gives a combined network whose furthest pair, for instance junction 3 of the first and junction 3 of the second, is the returned number of footpaths apart.

Example 2

Input
edges1 = [[0,1],[1,2],[2,3],[0,4],[4,5],[5,6]], edges2 = []
Output
6

The second network is a single junction, so its edge list is empty. The first network has two arms of three footpaths meeting at junction 0, so junctions 3 and 6 are 6 footpaths apart. Bridging the lone junction to junction 0 leaves that pair still 6 apart, which matches the returned value.

Example 3

Input
edges1 = [[0,1],[1,2],[2,3]], edges2 = [[0,1],[1,2],[2,3]]
Output
5

Both networks are chains of four junctions. Bridging junction 1 of the first to junction 1 of the second makes junction 3 of the first and junction 3 of the second the furthest pair, at the returned number of footpaths.

Constraints

  • 1 <= n <= 10^5, where n = edges1.length + 1
  • 1 <= m <= 10^5, where m = edges2.length + 1
  • 0 <= edges1.length <= 10^5 - 1
  • 0 <= edges2.length <= 10^5 - 1
  • edges1[i].length == 2
  • edges2[i].length == 2
  • 0 <= edges1[i][j] <= 10^5 - 1
  • 0 <= edges2[i][j] <= 10^5 - 1
  • Every endpoint listed in edges1 is below n and every endpoint listed in edges2 is below m.
  • edges1 always describes a connected acyclic network on its n junctions, and edges2 the same on its m junctions.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_diameter_after_merge(edges1: list[list[int]], edges2: list[list[int]]) -> int:
Java
public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2)

More on the same topics