Fewest bridges to connect every island
Once you can count the groups, one subtraction tells you how many links would join them all. About 8 minutes.
Groups minus one
A cluster of islands has a few bridges already. How many new bridges does it take so you can drive from any island to any other?
First, merge along every existing bridge and count the groups of islands that are already connected. Each new bridge can join two groups into one. So g groups need exactly g − 1 new bridges: no fewer will do, and that many is enough.
bridges = groups - 1
- groups
- 3
Merge every existing bridge first.
After the existing bridges, 4 separate groups of islands remain. How many new bridges are needed?
- A3
- B4
Show the answer
3. Each bridge joins two groups into one, so 3 bridges bring 4 groups down to 1.
Fewest bridges to connect every island
There are n islands, numbered 0 to n - 1, and edges lists existing bridges [a, b]. Return the fewest new bridges needed so that every island can be reached from every other island.
n = 5, edges = [[0, 1], [1, 2], [3, 4]] → 1
1 ≤ n ≤ 100,000 · 0 ≤ edges.length ≤ 100,000 · edges[i] has two different node numbers, each 0 ≤ x < n