概要

\(N\) 人の生徒が所属するグループを管理する問題です。「グループを合併する」という操作と、「ある生徒が属するグループの人数を答える」という操作を、大量のクエリ（指示）に対して高速に処理する必要があります。

考察

この問題で求められている操作は以下の2点です。 1. 併合 (Union): 2つのグループを1つにまとめる。 2. 判定・取得 (Find): ある要素がどのグループに属しているかを特定し、そのグループのサイズを取得する。

もし、各生徒がどのグループに属しているかを単純なリスト（例：group_id[生徒] = グループ番号）で管理しようとすると、グループを合併するたびに全生徒のグループ番号を書き換える必要が出てしまい、最悪の場合 \(O(N)\) の時間がかかります。クエリの回数を \(Q\) とすると、全体の計算量は \(O(NQ)\) となり、今回の制約（\(N, Q \leq 2 \times 10^5\)）では実行時間制限に間に合いません。

そこで、このような「グループの合併」と「所属の判定」を効率的に行うためのデータ構造である Union-Find（素集合データ構造） を利用します。

アルゴリズム

Union-Find

Union-Findは、要素を木構造で管理するデータ構造です。

• 根 (Root): 各グループの代表者となる要素です。同じグループに属する要素は、親を辿っていくと同じ「根」に到達します。
• 経路圧縮 (Path Compression): 根を探す際に、通った要素すべてを直接根に繋ぎ直す工夫です。これにより、次から根を探す手間が大幅に省けます。
• サイズによる合併 (Union by Size): 合併する際、要素数が少ない方の木を、要素数が多い方の木の根に繋ぐ工夫です。これにより、木の高さが不必要に高くなるのを防ぎます。

本問題では、各グループの人数を知る必要があるため、各グループの根の要素にそのグループの合計人数（size）を記録しておきます。

計算量

• 時間計算量: \(O(Q \alpha(N))\)
  • \(\alpha(N)\) はアッカーマン関数の逆関数で、実用上のあらゆる \(N\) に対して \(5\) 以下とみなせるほど非常に低速に増加する関数です。したがって、ほぼ \(O(Q)\) に近い速度で処理が可能です。
• 空間計算量: \(O(N)\)
  • 親要素を管理する配列 parent と、サイズを管理する配列 size を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

1. 高速な入出力: Pythonにおいて \(2 \times 10^5\) 規模の入出力を扱う場合、input() や print() を繰り返すと時間がかかります。sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力することで高速化を図っています。

2. 再帰制限の回避: Pythonの標準的な再帰による find 実装は、再帰回数の上限（Recursion Limit）に達してエラーになることがあります。今回のコードでは while ループを用いた反復的な実装にすることで、この問題を回避しています。

3. サイズの更新: グループ \(a\) と \(b\) を合併するとき、新しい根となる要素の size に、もう一方のグループの size を加算します。

   if root_a != root_b:
       # 小さい方を大きい方に繋ぐ
       if size[root_a] < size[root_b]:
           root_a, root_b = root_b, root_a
       parent[root_b] = root_a
       size[root_a] += size[root_b]
   

   ソースコード

import sys

def solve():
    # 入力を一度にすべて読み込み、スペースや改行で分割します。
    # これは競技プログラミングにおいてPythonで高速に入力を処理する一般的な手法です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # N: 生徒の人数, Q: 指示の回数
    n = int(next(it))
    q = int(next(it))
    
    # Union-Find（素集合データ構造）の初期化
    # parent[i] は生徒 i の親を表します。最初は自分自身が親（根）です。
    # size[i] は生徒 i が属するグループの人数を表します（i が根の場合のみ有効）。
    parent = list(range(n + 1))
    size = [1] * (n + 1)
    
    results = []
    
    for _ in range(q):
        query_type = next(it)
        
        if query_type == '1':
            # 指示 1: a と b のグループを合併する
            a = int(next(it))
            b = int(next(it))
            
            # a の属するグループの根を探す（経路圧縮を伴う反復的な実装）
            root_a = a
            while parent[root_a] != root_a:
                root_a = parent[root_a]
            curr = a
            while curr != root_a:
                parent[curr], curr = root_a, parent[curr]
            
            # b の属するグループの根を探す
            root_b = b
            while parent[root_b] != root_b:
                root_b = parent[root_b]
            curr = b
            while curr != root_b:
                parent[curr], curr = root_b, parent[curr]
            
            # 異なるグループに属している場合のみ合併する
            if root_a != root_b:
                # Union by Size: 小さい方のグループを大きい方のグループに繋ぐ
                if size[root_a] < size[root_b]:
                    root_a, root_b = root_b, root_a
                parent[root_b] = root_a
                size[root_a] += size[root_b]
                
        else:
            # 指示 2: x の属するグループの人数を出力する
            x = int(next(it))
            
            # x の属するグループの根を探す
            root_x = x
            while parent[root_x] != root_x:
                root_x = parent[root_x]
            # 経路圧縮
            curr = x
            while curr != root_x:
                parent[curr], curr = root_x, parent[curr]
            
            # 根におけるサイズを結果リストに追加
            results.append(str(size[root_x]))
    
    # 指示 2 に対する答えを一括して出力
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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