0772HardTreeDepth-First SearchBreadth-First SearchGraph Theory

Bridging Two Footpath Networks

Tracked in this browser only

Trains the technique from

LeetCode 3203Find Minimum Diameter After Merging Two Trees

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n + m): a constant number of breadth-first sweeps over each network.Space O(n + m) for the two adjacency lists and the sweep queues.

Measure each network on its own with two breadth-first sweeps: one from junction `0` to find a junction at maximum walk length, then one from that junction, whose deepest layer is the stretch. From a stretch `s` the network also has a junction whose walk length to every other junction is at most `(s + 1) // 2`, and planting the bridge at such a junction in both networks makes the longest crossing route `(s1 + 1) // 2 + (s2 + 1) // 2 + 1`. Neither existing network can shrink, so the answer is the largest of `s1`, `s2` and that crossing figure. Both sweeps run from an explicit queue rather than recursion so a chain of 10^5 junctions is safe.

Pythonentry point: minimum_diameter_after_merge

def _sweep(link, count, src):
    # Breadth-first layer walk from an explicit queue; returns a deepest junction
    # and its depth.
    seen = [-1] * count
    seen[src] = 0
    order = [src]
    head_at = 0
    best = src
    while head_at < len(order):
        cur = order[head_at]
        head_at += 1
        for nxt in link[cur]:
            if seen[nxt] < 0:
                seen[nxt] = seen[cur] + 1
                order.append(nxt)
                if seen[nxt] > seen[best]:
                    best = nxt
    return best, seen[best]


def _longest_walk(edges, count):
    if count <= 1:
        return 0
    link = [[] for _ in range(count)]
    for a, b in edges:
        link[a].append(b)
        link[b].append(a)
    far, _ = _sweep(link, count, 0)
    _, dist = _sweep(link, count, far)
    return dist


def minimum_diameter_after_merge(edges1, edges2):
    # Time O(n + m), space O(n + m). Both sweeps run off an explicit queue, so
    # a network shaped like one long chain of 10^5 junctions is fine.
    n = len(edges1) + 1
    m = len(edges2) + 1
    s1 = _longest_walk(edges1, n)
    s2 = _longest_walk(edges2, m)
    # A new footbridge planted at a most central junction of each network turns
    # the two halves plus the bridge into one candidate walk; the two existing
    # longest walks survive untouched.
    joined = (s1 + 1) // 2 + (s2 + 1) // 2 + 1
    return max(s1, s2, joined)

The obvious version

Relabel the second network's junctions after the first, then try every pair of bridge endpoints. For each pair, build the combined adjacency, run a breadth-first sweep from every junction, take the deepest layer seen as that combination's stretch, and keep the smallest across all pairs. Cubic-plus in the junction count, but it follows the definitions with no shortcuts.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_diameter_after_merge(edges1, edges2):
    n = len(edges1) + 1
    m = len(edges2) + 1
    total = n + m
    base = [[] for _ in range(total)]
    for a, b in edges1:
        base[a].append(b)
        base[b].append(a)
    for a, b in edges2:
        base[a + n].append(b + n)
        base[b + n].append(a + n)

    best = None
    for u in range(n):
        for v in range(n, total):
            link = [list(row) for row in base]
            link[u].append(v)
            link[v].append(u)
            widest = 0
            for src in range(total):
                dist = [-1] * total
                dist[src] = 0
                queue = [src]
                at = 0
                while at < len(queue):
                    cur = queue[at]
                    at += 1
                    for nxt in link[cur]:
                        if dist[nxt] < 0:
                            dist[nxt] = dist[cur] + 1
                            queue.append(nxt)
                    if dist[cur] > widest:
                        widest = dist[cur]
            if best is None or widest < best:
                best = widest
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in