概要

友人関係でつながった生徒たちの間に情報が拡散するとき、最終的に何人の生徒に情報が届くかを求める問題です。

考察

この問題では、友人関係によって生徒がグループ（連結成分）に分かれています。情報は友人関係を通じて同じグループ内に広まりますが、異なるグループには広まりません。

したがって、最初に情報を得た生徒たちが所属するグループの大きさ（人数）の合計が答えになります。

素朴な方法として、幅優先探索や深さ優先探索を使って情報をシミュレートすることも考えられますが、最大で \(N\) と \(M\) が \(2 \times 10^5\) なので、全探索は時間的に厳しく、計算量が \(O(N + M)\) でも定数倍の問題で間に合わない可能性があります。

そこで、友人関係を効率的にグループ分けするために、Union-Find（素集合データ構造） を用いるのが適切です。Union-Find を使うことで、友人関係をグループにまとめる処理と、所属するグループの確認を高速に行えます。

アルゴリズム

1. 友人関係を元に、Union-Find を使って生徒を連結成分（グループ）に分ける。
2. 最初に情報を得た生徒たちが所属するグループ（根）を特定する。
3. それらのグループに含まれる生徒数の合計を求める。

具体的には： - 各友人関係 \((u, v)\) に対して union(u, v) を呼び、同じグループにまとめる。 - 最初の情報を持つ生徒 \(S_i\) の属するグループの根を find(S_i) で求め、重複を避けて記録する。 - 各根に対応するグループのサイズを合計すれば答え。

例えば、以下のような入力の場合：

5 3 2
1 3
1 2
2 3
4 5

友人関係により生徒1, 2, 3が一つのグループになり、4, 5がもう一つのグループになります。最初に1と3に情報が渡るので、グループ1つのサイズ（3人）が答えになります。

計算量

• 時間計算量: \(O(N + M \cdot \alpha(N) + K \cdot \alpha(N))\)
  （\(\alpha(N)\) はアッカーマン関数の逆関数で、事実上定数とみなせる）
• 空間計算量: \(O(N)\)

実装のポイント

• Union-Find はパス圧縮とランク/サイズによるマージ最適化を使うことで、非常に高速に動作します。
• 根のサイズを保持しておけば、各連結成分の大きさをすぐに取得できます。
• 最初に情報を得た生徒が同じグループに属する場合もあるので、set を使って重複を除去する必要があります。

## ソースコード

```python
import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    S = list(map(int, data[3:3+K]))
    
    # Union-Find initialization
    parent = list(range(N + 1))
    size = [1] * (N + 1)
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # Path compression
        return parent[x]
    
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            # Union by size
            if size[root_x] < size[root_y]:
                root_x, root_y = root_y, root_x
            parent[root_y] = root_x
            size[root_x] += size[root_y]
    
    # Process friendships
    idx = 3 + K
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx + 1])
        idx += 2
        union(u, v)
    
    # Count unique root components that contain initial informants
    informed_roots = set()
    for s in S:
        informed_roots.add(find(s))
    
    # Sum sizes of those components
    total = sum(size[root] for root in informed_roots)
    print(total)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。