概要

\(N\) 個の頂点（島）と \(M\) 本の辺（橋の建設案）が与えられたとき、すべての頂点を連結にするために必要な辺の重み（コスト）の総和を最小化する「最小全域木（Minimum Spanning Tree）」を求める問題です。

考察

この問題を解くための重要なポイントは、「コストの低い橋から優先的に選ぶ」という貪欲法（グリーディ）の考え方です。

1. 最小全域木の性質: \(N\) 個の頂点をすべて連結にするには、少なくとも \(N-1\) 本の辺が必要です。コストを最小にするには、閉路（ぐるっと一周する経路）を作らないように辺を選んでいく必要があります。
2. 閉路の判定: コストが低い順に辺を見ていく際、その辺が結ぶ2つの島が「すでに同じグループに属しているか」を確認する必要があります。もし同じグループであれば、その橋を架けるのは無駄（閉路を作るだけ）なのでスキップします。
3. 効率的なグループ管理: 「2つの頂点が同じグループか判定する」「2つのグループを統合する」という操作を高速に行うために、Union-Find というデータ構造を使用するのが一般的です。

もし最終的に選んだ辺が \(N-1\) 本に満たない場合は、どのように橋を架けても全島を連結にできないため、-1 を出力します。

アルゴリズム

クラスカル法 (Kruskal’s Algorithm) を用いて解きます。手順は以下の通りです。

1. ソート: すべての橋の情報を、コスト \(C_i\) が小さい順に並べ替えます。
2. 初期化: \(N\) 個の島がそれぞれ独立したグループになるよう Union-Find を初期化します。
3. 辺の選択:
   • コストが小さい順に橋を取り出します。
   • その橋が結ぶ島 \(U_i\) と \(V_i\) が異なるグループに属しているか Union-Find で確認します。
   • 異なるグループであれば、その橋を建設し（コストを加算）、Union-Find で \(U_i\) と \(V_i\) を同じグループに統合します。
4. 終了判定:
   • 選んだ橋の本数が \(N-1\) 本に達したら、その時点の合計コストを出力します。
   • すべての橋を調べ終えても \(N-1\) 本に達しない場合は、-1 を出力します。

計算量

• 時間計算量: \(O(M \log M)\)
  • 橋のソートに \(O(M \log M)\) かかります。
  • Union-Find の操作（ならし計算量）はほぼ定数時間 \(O(\alpha(N))\) であるため、全体ではソートの計算量が支配的になります。
• 空間計算量: \(O(N + M)\)
  • 橋の情報を保存するリストに \(O(M)\)、Union-Find の親ノードを管理する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• \(N=1\) のケース: 島が1つしかない場合、最初から連結であるためコストは 0 になります。このケースを考慮しておくと安全です。

• Union-Find の最適化: 実装では「経路圧縮（Path Compression）」と「ランクによる統合（Union by Rank）」を併用することで、非常に高速な動作を実現しています。

• 高速な入力処理: Pythonで \(M\) が大きい場合、input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が実行時間を短縮できます。

  ソースコード

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()

この解説は gemini-3-flash-preview によって生成されました。