Merge Networks

Problem Statement

Merge Networks Problem Description A mapping team is planning roads for two separate regions. Each region is described by a network of places: networkA and networkB . The two networks are completely separate -- place 1 of networkA and place 1 of networkB are different places, and no road currently runs between the two networks. Each network is an unweighted tree : a network with k places has exactly k - 1 roads, and every place can be reached from every other place in that network. (inferred -- the source declares the edge arrays with exactly networkA_nodes - 1 and networkB_nodes - 1 entries, and a maximum distance only exists if every place is reachable, so each network is connected and acyclic.) The team will build exactly one new road joining one place of networkA to one place of networkB. After that road is built the two networks form a single connected network. The distance between two places is the number of roads on the simple path between them (a simple path repeats no place).