概要

友人関係を辺とする無向グラフで、最初に情報を知った生徒集合 \(S\) と同じ連結成分に属する生徒の総数を求める問題です。

考察

情報は「友人関係で直接または間接的につながっている」生徒へ必ず伝わるので、結局 情報が届く範囲 = 初期に知っている生徒が属する連結成分全体 になります。

たとえば、グラフがいくつかの連結成分（グループ）に分かれているとき、初期メンバーが1人でも含まれる成分は、その成分の全員に情報が届きます。逆に、初期メンバーがいない成分には一切届きません。

素朴に考えると、 - 各初期生徒 \(s \in S\) から BFS/DFS をして到達可能な頂点を全部数える
という方法が思いつきますが、初期生徒が多いと同じ成分を何度も探索してしまい、最悪で \(O(K(N+M))\) になり得て間に合いません（\(N,M \le 2\times 10^5\) なので厳しい）。

そこで、グラフの「連結成分」を高速に扱える Union-Find（Disjoint Set Union, DSU） を使い、 1. まず全辺を使って連結成分を構築 2. 初期生徒が含まれる成分を印付け 3. 印が付いた成分のサイズを合計 とすれば、無駄な重複探索なく解けます。

アルゴリズム

Union-Find を用いて以下を行います。

1. Union-Find の初期化
   各頂点は最初は別集合。配列 parent を用い、根では parent[root] = -size（集合サイズの負数）として管理します。

2. 全ての友人関係を union
   各辺 \((u_i, v_i)\) について union(u_i, v_i) を行い、同じ連結成分にまとめます。
   （サイズの大きい集合を根にする union-by-size と、経路圧縮を併用）

3. 初期生徒が属する連結成分に印を付ける
   各 \(s \in S\) について根 find(s) を求め、その根に対して has[root] = True とします。
   これで「この成分には初期生徒がいる」が判定できます。

4. 印が付いた成分のサイズを合計して答えにする
   1 から \(N\) まで走査し、「根（parent[i] < 0）かつ has[i] == True」なら、その成分サイズ -parent[i] を加算します。

計算量

• 時間計算量: \(O((N+M)\alpha(N))\)
  （Union-Find の find/union はならし計算量でほぼ定数の \(\alpha(N)\)）
• 空間計算量: \(O(N)\)
  （parent, has など）

実装のポイント

• Union-Find の根で サイズを負で持つ 実装にすると、成分サイズを -parent[root] で即座に取り出せて便利です。

• has[find(s)] = True のように、必ず根に対して印を付けるのが重要です（途中ノードに付けると成分判定が崩れます）。

• 入力が最大 \(2\times 10^5\) 行規模なので、sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    S = [next(it) for _ in range(K)]

    parent = [-1] * (N + 1)

    def find(x):
        while parent[x] >= 0:
            if parent[parent[x]] >= 0:
                parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a = find(a)
        b = find(b)
        if a == b:
            return
        if parent[a] > parent[b]:  # size(a) < size(b)
            a, b = b, a
        parent[a] += parent[b]
        parent[b] = a

    for _ in range(M):
        u = next(it)
        v = next(it)
        union(u, v)

    has = [False] * (N + 1)
    for s in S:
        has[find(s)] = True

    ans = 0
    for i in range(1, N + 1):
        if parent[i] < 0 and has[i]:
            ans += -parent[i]

    print(ans)

if __name__ == "__main__":
    main()

---

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