\(N\) 頂点 \(M\) 辺の、頂点 \(A_i\) から頂点 \(B_i\) に有向辺が張られたようなグラフを考えます。この問題の答えはこのグラフで頂点 \(1\) から到達可能な頂点の個数です。

そして、これは幅優先探索を用いて解くことができます。具体的には、以下のようにして解くことができます：

• 到達済みの頂点集合を \(S\) で持つ。はじめ、\(S=\lbrace 1\rbrace\) である。
• 到達済みであるが、まだその頂点から探索していない頂点集合 \(q\) を持つ。はじめ、\(q=\lbrace 1\rbrace\) である。
• \(q\) が空でない限り、以下の操作を繰り返す。
  • \(q\) の要素を \(1\) つ取り、\(x\) とする。\(x\) を \(q\) から削除する。
  • \(x\) と辺で繋がっている頂点 \(y\) それぞれに対し、以下の操作を行う。
    • \(y\) が既に到達済み、つまり \(y \in S\) であるなら何もしない。
    • 到達済みでない場合、\(S\) に \(y\) を入れ \(q\) に \(y\) を入れる。

以上を適切に実装することでこの問題に正答することができます。

実装上は、\(S\) を長さ \(N\) の bool 配列で \(S[i]\) が True なら \(i \in S\) 、False なら \(i \not \in S\) と表現し、さらに \(q\) を queue で表現するのが一般的です。

実装例(Python3)

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    g[x - 1].append(y - 1)
q = deque()
d = [False] * n
q.append(0)
d[0] = True
while q:
    x = q.popleft()
    for i in g[x]:
        if d[i]:
            continue
        d[i] = True
        q.append(i)
print(d.count(True))