In this problem, given a directed graph with $n$ nodes and $m$ edges, we need to return "YES" if we can travel between all pairs of vertices $u, v$ or "NO" and give the pair of vertices we can't travel between otherwise.

Main Idea

The theorem 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
#include <bits/stdc++.h>  // see C++ Tips & Tricks
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

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)

Copy
import java.io.*;
import java.util.*;

public class FlightRoutesCheck {
	static int n, m;
	static boolean[] vis;

	public static void main(String[] args) {
		Kattio io = new Kattio();
		n = io.nextInt();

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