概要

\(N\) 人の選手が所属するチームを合併させながら、チームごとに「旗の色」を上書きしていく問題です。最終的に存在する各チームが持っている旗の色を調べ、その色の種類数を求めます。

考察

この問題のポイントは、「チームの合併」と「色の更新」をいかに効率的に管理するかにあります。

1. チームの合併（Union-Findの活用） 「選手 \(U_i\) と \(V_i\) が所属するチームを合併する」という操作は、データ構造の Union-Find (素集合データ構造) を使うことで非常に高速に処理できます。Union-Find を使うと、各選手がどのグループ（チーム）に属しているかを「代表者（根）」という形で管理できます。

2. 色の管理 各チームは一つの色を持ちます。チームの合併が行われるたびに色が上書きされるため、「その時点でのチームの代表者」に対して色を紐付けるのが効率的です。

   • 合併が行われる場合：新しいチームの代表者に色 \(C_i\) を設定します。
   • すでに同じチームの場合：現在の代表者の色を \(C_i\) に更新します。

3. なぜ単純な配列ではダメなのか？ もし「各選手がどの色を持っているか」を全員分書き換えていると、1回の操作に最大 \(O(N)\) かかってしまい、全体で \(O(NM)\) となり間に合いません。Union-Find を使い、代表者だけが色情報を持つようにすることで、大幅な高速化が可能になります。

アルゴリズム

以下の手順で解を求めます。

1. 初期化:
   • \(N\) 個の要素を持つ Union-Find 木を作成します。
   • 各チームの色を保持する配列 color を用意し、初期値を「未設定」を意味する -1 にします。
2. 操作の処理: \(M\) 回の各操作 \((U_i, V_i, C_i)\) について以下を行います。
   • \(U_i\) と \(V_i\) の代表者 \(root\_u, root\_v\) を探します。
   • 2人が異なるチームにいる場合：
     • 2つの木を合併させ、新しい代表者を決めます（Union by Rank）。
     • 新しい代表者の color を \(C_i\) に更新します。
   • 2人がすでに同じチームにいる場合：
     • その代表者の color を \(C_i\) に更新します。
3. 集計:
   • すべての選手 \(i = 1 \dots N\) について確認します。
   • もし選手 \(i\) がそのチームの代表者（parent[i] == i）であり、かつ color[i] が -1 でなければ、その色を集合（set）に追加します。
   • 最後に集合の要素数を出力します。

計算量

• 時間計算量: \(O(M \alpha(N) + N)\)
  • \(M\) 回の Union-Find 操作には \(O(M \alpha(N))\) かかります（\(\alpha\) はアッカーマン関数の逆関数で、実用上はほぼ定数です）。
  • 最後の集計に \(O(N)\) かかります。
  • 全体として非常に高速に動作します。
• 空間計算量: \(O(N)\)
  • Union-Find 用の配列（parent, rank）および色管理用の配列で \(O(N)\) のメモリを使用します。

実装のポイント

• 反復型 Union-Find: Python では再帰の深さ制限があるため、find 操作（代表者探し）を while ループを用いた反復型で実装することで、ランタイムエラーを防いでいます。

• 経路圧縮 (Path Compression): find 操作の際、親を直接代表者に繋ぎ変えることで、その後の操作を高速化しています。

• 高速な入出力: \(N, M\) が大きいため、sys.stdin.read().split() を用いて一気に入力を読み込む工夫をしています。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、スペースで分割してリストにする
    # 大量の入力を処理する場合、この方法が一般的に高速です
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    # 整数に変換
    data = list(map(int, input_data))
    
    N = data[0]
    M = data[1]
    
    # Union-Find用のデータ構造
    # parent[i]: 選手 i が属するチームの親。自分自身ならそのチームの代表者
    # rank[i]: 木の高さ（Union by Rank用）
    # color[i]: 代表者 i が率いるチームの現在の旗の色。-1は未設定を表す
    parent = list(range(N + 1))
    rank = [0] * (N + 1)
    color = [-1] * (N + 1)
    
    data_idx = 2
    for _ in range(M):
        # 各操作の情報を取得
        if data_idx + 2 >= len(data):
            break
        u = data[data_idx]
        v = data[data_idx+1]
        c = data[data_idx+2]
        data_idx += 3
        
        # 選手 u が属するチームの代表者を見つける（経路圧縮付き、反復型）
        root_u = u
        while parent[root_u] != root_u:
            root_u = parent[root_u]
        curr = u
        while curr != root_u:
            parent[curr], curr = root_u, parent[curr]
            
        # 選手 v が属するチームの代表者を見つける（経路圧縮付き、反復型）
        root_v = v
        while parent[root_v] != root_v:
            root_v = parent[root_v]
        curr = v
        while curr != root_v:
            parent[curr], curr = root_v, parent[curr]
        
        if root_u != root_v:
            # 異なるチームを合併する（Union by Rank）
            if rank[root_u] < rank[root_v]:
                root_u, root_v = root_v, root_u
            parent[root_v] = root_u
            if rank[root_u] == rank[root_v]:
                rank[root_u] += 1
            # 合併後のチーム（新しい代表者 root_u）に新しい色を設定
            # 以前の root_v の色は、root_v が代表者でなくなったため無視される
            color[root_u] = c
        else:
            # すでに同じチームに属している場合、そのチームの色を更新
            color[root_u] = c
            
    # すべての操作終了後、各チーム（代表者）の旗の色を確認
    unique_colors = set()
    for i in range(1, N + 1):
        # parent[i] == i ならば、その選手はチームの代表者
        if parent[i] == i:
            # color[i] が -1 でなければ、そのチームには旗の色が設定されている
            if color[i] != -1:
                unique_colors.add(color[i])
    
    # 異なる色の種類数を出力
    sys.stdout.write(str(len(unique_colors)) + '\n')

if __name__ == '__main__':
    solve()

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