Overview

Given a set of candidate bridges, the problem asks to select some of them so that all islands can reach each other (i.e., the graph becomes connected), while minimizing the total cost. If it is impossible to make the graph connected, output -1.

Approach

If we consider islands as vertices and bridge proposals as edges (with costs), then “finding the minimum cost to connect all vertices” is exactly the problem of finding a Minimum Spanning Tree (MST).

• To create a connected graph with minimum cost, unnecessary edges (those that create cycles) are not needed.
  A connected graph on \(N\) vertices with no cycles (a tree) always has exactly \(N-1\) edges, and with fewer edges it cannot be connected.
• Therefore, we need to find “\(N-1\) edges that form a connected graph with minimum cost.”

Naively enumerating all possible subsets of edges is infeasible since there can be up to \(2\times 10^5\) edges, leading to combinatorial explosion. Also, simply taking edges in order of increasing cost without any check would include edges that create cycles, making it impossible to achieve the minimum cost or properly manage the required number of edges.

The key observation here is:

• Examine edges in order of increasing cost and adopt an edge if it does not create a cycle.
  This strategy (Kruskal’s algorithm) correctly constructs the MST.
• To determine “whether an edge creates a cycle,” we can efficiently check whether two vertices are currently in the same connected component using a Union-Find (DSU) data structure.

Whether the graph has been made connected can be determined by checking if the number of adopted edges has reached \(N-1\) (if not, the graph cannot be connected).

Algorithm

We construct the minimum spanning tree using Kruskal’s algorithm + Union-Find.

1. Sort all bridge proposals (edges) in ascending order of cost \(C_i\).
2. Initialize the Union-Find (each island starts in its own connected component).
3. Examine edges \((u,v,c)\) in sorted order.
   • If \(u\) and \(v\) are in different connected components, adopt the edge, add \(c\) to the total cost, and merge the components using Union-Find.
   • If they are in the same component, adopting the edge would create a cycle, so skip it.
4. Stop once the number of adopted edges reaches \(N-1\).
5. Finally:
   • If \(N=1\), the graph is already connected, so the answer is \(0\).
   • If the number of adopted edges is \(N-1\), output the total cost.
   • Otherwise, output -1 (the graph cannot be made connected with the given candidates).

(Simple example)
With 4 islands, examining edges in order of increasing cost and selecting only those that do not create cycles, the total cost when all islands become connected with exactly 3 edges (\(N-1\) edges) is the minimum.

Complexity

• Time complexity: \(O(M\log M)\) (dominated by sorting the edges; Union-Find operations are nearly \(O(1)\))
• Space complexity: \(O(N+M)\) (for the Union-Find and edge list)

Implementation Notes

• Since island numbers in the input are \(1\)-indexed, convert them to \(0\)-indexed in the implementation (u-1, v-1).
• The Union-Find should incorporate:
  • Path compression (to speed up find)
  • Union by size (attaching the smaller tree under the larger tree)

This ensures fast and stable performance. - Once \(N-1\) edges have been adopted, there is no need to examine further edges, so an early break reduces unnecessary work. - When \(N=1\), no edges are needed, so the answer is always \(0\) (including this special case ensures safety).

Source Code

import sys

class DSU:
    __slots__ = ("parent", "size")
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra = self.find(a)
        rb = self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, c = map(int, input().split())
        edges.append((c, u - 1, v - 1))
    edges.sort()

    dsu = DSU(N)
    total = 0
    cnt = 0
    for c, u, v in edges:
        if dsu.union(u, v):
            total += c
            cnt += 1
            if cnt == N - 1:
                break

    if N == 1:
        print(0)
    elif cnt == N - 1:
        print(total)
    else:
        print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.