CSES - Flight Routes Check

Authors: Michael Cao, Nathan Gong

In this problem, given a directed graph with nn nodes and mm edges, we need to return "YES" if we can travel between all pairs of vertices u,vu, 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 can[u][v]\texttt{can[u][v]} is true if you can go from vertex uu to vertex vv through a series of edges. Additionally, let's define the directed graph given in the statement as GG and the reverse of it (where an edge uvu \rightarrow v becomes vuv \rightarrow u) as GG'. Then, if can[1][x]\texttt{can[1][x]} for 1xn1 \leq x \leq n in both GG and GG', the answer is "YES".

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

Proof

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

Implementation

C++

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

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!