Overview

Given \(N\) islands and candidate bridges with costs connecting them, find the minimum cost required to make all islands mutually reachable. If it is impossible, output \(-1\).

Analysis

This problem reduces to finding the Minimum Spanning Tree (MST) of a graph. If we consider islands as vertices, bridges as edges, and costs as weights in an undirected graph, then “making all islands mutually reachable” = “making the graph connected” = “constructing a spanning tree.” Furthermore, since we want to minimize the cost, we need to find the “minimum spanning tree.”

A naive approach would be to try all edges and check connectivity each time, but when the number of edges is large (up to \(2 \times 10^5\)), this is extremely inefficient and cannot be solved within the time limit. To efficiently manage connectivity at minimum cost, it is common to use a data structure called Union-Find (Disjoint Set Union).

To achieve the minimum cost, we can sort the edges in ascending order of cost and greedily select them (Kruskal’s algorithm). This allows us to obtain a minimum-cost spanning tree without selecting unnecessary edges.

Finally, if the number of connected components does not become 1, it is impossible to connect all islands, so we output -1.

Algorithm

This problem uses Kruskal’s algorithm.

Steps:

1. Sort all edges in ascending order of cost.
2. Prepare a Union-Find structure where initially all vertices belong to independent sets.
3. Iterate through edges in order of increasing cost.
   • If the two endpoints of an edge belong to different sets (= the unite operation succeeds), adopt that edge and add its cost.
   • Terminate once all vertices belong to a single set.
4. If the final number of connected components is not 1, output -1.

Complexity

• Time complexity: \(O(M \log M)\) (Sorting edges takes \(O(M \log M)\), Union-Find operations take approximately \(O(\alpha(N))\) each, and the dominant term overall is the sorting)
• Space complexity: \(O(N + M)\) (For the Union-Find management area and the edge list)

Implementation Notes

• Convert vertex numbers to 0-indexed (change input from \(1\) to \(N\) into \(0\) to \(N-1\)).

• Union-Find is optimized for speed by using path compression and union by rank.

• Use a components variable to track the number of connected components, and terminate as soon as it reaches 1 to avoid unnecessary processing.

• Note that if the graph is already connected from the start (\(N = 1\)), the cost is 0.

  Source Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr != yr:
            if self.rank[xr] < self.rank[yr]:
                xr, yr = yr, xr
            self.parent[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1
            self.components -= 1
            return True
        return False

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    edges = []
    idx = 2
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx+1]) - 1
        c = int(data[idx+2])
        edges.append((c, u, v))
        idx += 3
    
    edges.sort()
    
    uf = UnionFind(N)
    total_cost = 0
    
    for cost, u, v in edges:
        if uf.unite(u, v):
            total_cost += cost
            if uf.components == 1:
                print(total_cost)
                return
    
    if N == 1:
        print(0)
    else:
        print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.