Overview

Given \(N\) vertices (islands) and \(M\) edges (bridge construction proposals), this problem asks us to find the Minimum Spanning Tree (MST) — that is, to minimize the total sum of edge weights (costs) needed to connect all vertices.

Key Observations

The important point for solving this problem is the greedy approach of “prioritizing bridges with lower cost.”

1. Properties of Minimum Spanning Trees: To connect all \(N\) vertices, at least \(N-1\) edges are required. To minimize cost, we need to select edges without creating cycles (paths that loop back to the starting point).
2. Cycle Detection: When examining edges in order of increasing cost, we need to check whether the two islands connected by an edge “already belong to the same group.” If they are in the same group, building that bridge would be wasteful (it would only create a cycle), so we skip it.
3. Efficient Group Management: To efficiently perform the operations “determine whether two vertices belong to the same group” and “merge two groups,” it is standard to use the Union-Find data structure.

If the number of selected edges ends up being fewer than \(N-1\), it is impossible to connect all islands regardless of which bridges are built, so we output -1.

Algorithm

We solve this using Kruskal’s Algorithm. The procedure is as follows:

1. Sort: Sort all bridge information in ascending order of cost \(C_i\).
2. Initialization: Initialize the Union-Find so that each of the \(N\) islands starts as its own independent group.
3. Edge Selection:
   • Extract bridges in order of increasing cost.
   • Use Union-Find to check whether islands \(U_i\) and \(V_i\) connected by the bridge belong to different groups.
   • If they belong to different groups, build the bridge (add its cost), and merge \(U_i\) and \(V_i\) into the same group using Union-Find.
4. Termination Check:
   • If the number of selected bridges reaches \(N-1\), output the total cost at that point.
   • If all bridges have been examined without reaching \(N-1\) selected bridges, output -1.

Complexity

• Time Complexity: \(O(M \log M)\)
  • Sorting the bridges takes \(O(M \log M)\).
  • Union-Find operations have an amortized time complexity of nearly constant \(O(\alpha(N))\), so the overall complexity is dominated by the sorting step.
• Space Complexity: \(O(N + M)\)
  • \(O(M)\) memory is used for the list storing bridge information, and \(O(N)\) memory is used for the array managing parent nodes in Union-Find.

Implementation Notes

• Case \(N=1\): If there is only one island, it is already connected from the start, so the cost is 0. It is safe to handle this case explicitly.

• Union-Find Optimization: In the implementation, combining “Path Compression” and “Union by Rank” achieves extremely fast performance.

• Fast Input Processing: In Python, when \(M\) is large, reading all input at once using sys.stdin.read().split() is faster than calling input() repeatedly, reducing execution time.

  Source Code

import sys

def solve():
    # 入力を一度に読み込み、空白で分割してトークン化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して各トークンを整数に変換しながら取得します
    it = map(int, input_data)
    
    try:
        N = next(it)
        M = next(it)
    except StopIteration:
        return
    
    # 島が1つの場合は、すでに連結しているためコストは0です
    if N == 1:
        print(0)
        return

    # 各橋の建設案を (コスト, 島1, 島2) の形式でリストに格納します
    edges = []
    for _ in range(M):
        try:
            u = next(it)
            v = next(it)
            c = next(it)
            edges.append((c, u, v))
        except StopIteration:
            break
            
    # クラスカル法: コストが小さい順に橋をソートします
    edges.sort()
    
    # Union-Find（素集合データ構造）の初期化
    parent = list(range(N + 1))
    rank = [0] * (N + 1)

    def find(i):
        # 経路圧縮を用いた反復的なfind操作
        root = i
        while parent[root] != root:
            root = parent[root]
        curr = i
        while parent[curr] != root:
            next_node = parent[curr]
            parent[curr] = root
            curr = next_node
        return root
        
    def union(i, j):
        # ランクによる統合を用いたunion操作
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            if rank[root_i] < rank[root_j]:
                parent[root_i] = root_j
            elif rank[root_i] > rank[root_j]:
                parent[root_j] = root_i
            else:
                parent[root_i] = root_j
                rank[root_j] += 1
            return True
        return False
        
    total_cost = 0
    num_edges_added = 0
    
    # コストの小さい順に橋を検討し、閉路を作らない場合に採用します
    for c, u, v in edges:
        if union(u, v):
            total_cost += c
            num_edges_added += 1
            # すべての島を連結にするには N-1 本の橋が必要です
            if num_edges_added == N - 1:
                break
                
    # N-1 本の橋を採用できた場合は最小総コストを出力し、そうでない場合は -1 を出力します
    if num_edges_added == N - 1:
        print(total_cost)
    else:
        print(-1)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.