10996. Flight routes check

There are n cities and m flights. Your task is to determine whether it is possible, using the available flights, to travel from any city to any other city.

Input. The first line contains two integers n and  m – the number of cities and flights. The cities are numbered with integers 1, 2, ..., n.

The next  lines describe the flights. Each line contains two integers a and b, meaning that there is a flight from city a to city b. All flights are one-way.

Output. Print “YES” if all routes are possible, and “NO” otherwise. In the latter case, also print two cities a and b such that it is impossible to travel from a to b.

Sample input	Sample output
4 5 1 2 2 3 3 1 1 4 3 4	NO 4 2

SOLUTION

graphs, SCC

Algorithm analysis

In the problem, you are required to print “YES” if the graph is strongly connected.

A graph is called strongly connected if, for any vertex v, the following conditions hold:

· all other vertices of the graph are reachable from vertex v;

· vertex v is reachable from every other vertex. In other words, from any vertex there exists a path to v, which is equivalent to reachability in the reversed graph.

Fix vertex v = 1 and verify that these conditions are satisfied.

Algorithm implementation

The input graph is stored as an adjacency list g. The reversed graph is stored as an adjacency list gr.

vector<vector<int> > g, gr;

vector<int> used;

The function dfs1 performs a depth-first search

void dfs1(int v)

{

used[v] = 1;

for (int to : g[v])

if (!used[to]) dfs1(to);

}

The function dfs2 performs a depth-first search on the reversed graph.

void dfs2(int v)

{

used[v] = 1;

for (int to : gr[v])

if (!used[to]) dfs2(to);

}

The main part of the program. Read the input data and build the reversed graph.

scanf("%d %d", &n, &m);

g.resize(n + 1);

gr.resize(n + 1);

for (i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

g[a].push_back(b);

gr[b].push_back(a);

}

Run a depth-first search on the original graph starting from vertex 1.

used.resize(n + 1);

dfs1(1);

for (i = 1; i <= n; i++)

if (used[i] == 0) break;

If vertex i is unreachable (used[i] = 0), then traveling between cities 1 and i is impossible.

if (i <= n)

{

printf("NO\n%d %d\n", 1, i);

return 0;

}

Run a depth-first search on the reversed graph starting from vertex 1.

used.clear();

used.resize(n + 1);

dfs2(1);

for (i = 1; i <= n; i++)

if (used[i] == 0) break;

If vertex i is unreachable from 1 in the reversed graph (i.e., used[i] = 0), then traveling between cities i and 1 is impossible.

if (i <= n)

{

printf("NO\n%d %d\n", i, 1);

return 0;

}

The graph is strongly connected. Print “YES”.

printf("YES\n");