Explanation

The theorem being used here is that if one vertex can both reach and be reached by all others, then every vertex in this graph can reach all others.

Let's say $\texttt{can[u][v]}$ is true if you can go from vertex $u$ to vertex $v$ through a series of edges. Additionally, let's define the directed graph given in the statement as $G$ and the reverse of it (where an edge $u \rightarrow v$ becomes $v \rightarrow u$) as $G'$. Then, if $\texttt{can[1][x]}$ for $1 \leq x \leq n$ in both $G$ and $G'$, the answer is "YES".

To compute $\texttt{can[1][x]}$, we can run a dfs from from vertex $1$ and check if you can reach vertex $x$ for all $1 \leq x \leq n$. If we can't, then print $1$ $x$ if you're running the DFS on $G$ and $x$ $1$ otherwise.

Proof

Let's do a proof by contradiction. Assume that $\texttt{can[1][x]}$ is true for all vertices $x$ in both $G$ and $G'$, and there exists a pair of vertices $u, v$ such that $\texttt{can[u][v]} = \texttt{false}$. Since $\texttt{can[1][u]}$ is true in $G'$, then $\texttt{can[u][1]}$ must be true in $G$. Additionally, $\texttt{can[1][v]}$ must be true in $G$. So, you can travel from $u \rightarrow 1 \rightarrow v$, which contradicts the statement that $\texttt{can[u][v]} = \texttt{false}$. Thus, $\texttt{can[u][v]}$ is true for all vertices $u, v$.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
from typing import List, Set

n, m = map(int, input().split())

forward_graph = [[] for _ in range(n)]
reverse_graph = [[] for _ in range(n)]

for _ in range(m):
	a, b = map(int, input().split())
	forward_graph[a - 1].append(b - 1)

The problem can also be solved using strongly connected components (SCC).