概要

「チームの合併」と「合併後チームの色の上書き」を大量に処理したあと、最終的に存在する各チームの旗色の種類数を数える問題です。
チーム管理には Union-Find（DSU）を使うのが最適です。

考察

この問題の本質は、選手ごとの所属ではなく「どの連結成分（チーム）に属しているか」を高速に管理することです。
操作ごとに

1. \(U_i\) と \(V_i\) の属するチームを統合（同じならそのまま）
2. そのチームの色を \(C_i\) に上書き

を行います。

重要な気づき

• 各操作は「2頂点を結ぶ」ので、チームは連結成分として扱える。
• 連結成分の管理は Union-Find が定番。
• 色は「チーム単位」で1つだけ持てばよい（メンバーごとに持つ必要はない）。

素朴解が厳しい理由

例えば毎回、 - 全選手を走査してチームを再構築する - 2チームのメンバー一覧をマージする

のような実装をすると、最悪で \(O(NM)\) に近くなり、\(N=2\times10^5,\ M=1.5\times10^5\) では間に合いません。

どう解決するか

Union-Find で以下を管理します。

• parent[x]: 親
• size[x]: 根が x の集合サイズ（union by size 用）
• color[x]: 根 x が表すチームの現在色（未設定は 0）

操作 \((u,v,c)\) ごとに根 ru, rv を求め、

• ru != rv なら小さい集合を大きい集合へ併合し、新しい根の色を c にする
• ru == rv ならその根の色を c で上書き

最後に「根であり、色が未設定でないもの」だけを見て色を set に入れれば、異なる色数が求まります。

アルゴリズム

1. 初期化
   
   • 各選手は自分自身を根とする集合
     
   • color はすべて 0（未設定）
2. 各操作 \((u,v,c)\) を処理
   
   1. ru = find(u), rv = find(v)
   2. ru != rv の場合
      
      • size が大きい方を新しい根にする（union by size）
      • 親をつなぐ
      • サイズ更新
      • 新しい根の color を c にする
   3. ru == rv の場合
      
      • その根の color を c にする
3. 全要素 i=1..N について
   
   • parent[i] == i（根）かつ color[i] != 0 のとき seen に追加
4. len(seen) を出力

計算量

• 時間計算量: \(O((N+M)\alpha(N))\)（ほぼ線形）
• 空間計算量: \(O(N)\)

実装のポイント

• find は経路圧縮つきで実装し、高速化する。

• 併合時は size によるマージで木の高さを抑える。

• 色は「根にのみ意味がある」ので、最終集計でも根だけ見る。

• 色の未設定判定に 0 を使うため、入力色 C_i が正整数である制約と矛盾しない。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())

    parent = list(range(N + 1))
    size = [1] * (N + 1)
    color = [0] * (N + 1)  # 0 means unset

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for _ in range(M):
        u, v, c = map(int, input().split())
        ru = find(u)
        rv = find(v)

        if ru != rv:
            if size[ru] < size[rv]:
                ru, rv = rv, ru
            parent[rv] = ru
            size[ru] += size[rv]
            color[ru] = c
        else:
            color[ru] = c

    seen = set()
    for i in range(1, N + 1):
        if parent[i] == i and color[i] != 0:
            seen.add(color[i])

    print(len(seen))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。