Consider a graph with \(N\) vertices and \(M\) edges, where is an edge from vertex \(A_i\) to vertex \(B_i\) for each \(i\). The answer to the problem is the number of vertices reachable from vertex \(i\) on this graph.

This can be solved by BFS (Breadth-First Search). Specifically, it can be solved by the following steps:

• Maintain the set of already reached vertices \(S\). Initially, \(S=\lbrace 1\rbrace\).
• Maintain the set of vertices that are already reached, but a search has not been performed yet from that vertex. Initially, \(q=\lbrace 1\rbrace\).
• While \(q\) is nonempty, repeat the following procedure.
  • Take an element \(x\) of \(q\). Remove \(x\) from \(q\).
  • For each vertex \(y\) directly connected to \(x\), do the following:
    • If \(y\) is already reached, i.e. if \(y \in S\), do nothing.
    • Otherwise, insert \(y\) to \(S\), and insert \(y\) to \(q\).

The problem can be solved by appropriately implementing this.

In actual implementation, it is a general idea to represent \(S\) as a length-\(N\) boolean array, where \(S[i] = \)True signifies \(i \in S\) and False signifies \(i \not \in S\); and also, to represent \(q\) as a queue.

Sample code (Python 3)

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))