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 pair of vertices we can't travel between otherwise.

Main Idea

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

To compute $\text{can[1][x]}$, we can run a dfs from from vertex $1$ and check if you can reach vertex $x$ for all $1\le x\le 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 $\text{can[1][x]}$ is true for all vertices $x$ in both $G$ and $G^{\prime }$, and there exists a pair of vertices $u,v$ such that $\text{can[u][v]}=0$. Since $\text{can[1][u]}$ is true in $G^{\prime }$, then $\text{can[u][1]}$ must be true in $G$. Additionally, $\text{can[1][v]}$ must be true in $G$. So, you can travel from $u\to 1\to v$, which contradicts the statement that $\text{can[u][v]}=0$. Thus, $\text{can[u][v]}=1$ for all vertices $u,v$.

Example Code

1#include <bits/stdc++.h> // see C++ Tips & Tricks
2using namespace std;
3
4using ll = long long;
5
6using vi = vector<int>;
7#define pb push_back
8#define rsz resize
9#define all(x) begin(x), end(x)
10#define sz(x) (int)(x).size()