# CSES - Flight Routes Check

Authors: Michael Cao, Nathan Gong

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

C++

#include <bits/stdc++.h> // see C++ Tips & Tricksusing 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()

Python

from typing import List, Setn, 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)

Java

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

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!