10996. Проверка авиамаршрутов

Имеются n городов и m рейсов. Ваша задача – проверить, можно ли по доступным рейсам добраться из любого города в любой другой.

Вход. Первая строка содержит два целых числа n и m: количество городов и рейсов. Города пронумерованы числами 1, 2, ..., n.

Затем идут m строк с описанием перелетов. Каждая строка содержит два целых числа a и b, означающих что имеется рейс из города a в город b. Все рейсы односторонние.

Выход. Выведите “YES”, если все маршруты возможны, и “NO” в противном случае. В последнем случае также выведите два города a и b, между которыми путешествие невозможно.

Пример входа	Пример выхода
4 5 1 2 2 3 3 1 1 4 3 4	NO 4 2

РЕШЕНИЕ

графы, сильная связность

Анализ алгоритма

В задаче следует вывести “YES”, если граф сильно связный. Граф является сильно связным, если:

· для любой вершины v графа все остальные вершины достижимы из нее.

· вершина v достижима из любой другой вершины. Другими словами, любая вершина достижима из v по обратным ребрам.

Выберем в качестве v = 1 и проверим эти условия.

Реализация алгоритма

Входной граф храним в списке смежности g. Обратный граф храним в gr.

vector<vector<int> > g, gr;

vector<int> used;

Функция dfs1 реализует поиск в глубину.

void dfs1(int v)

{

used[v] = 1;

for (int to : g[v])

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

}

Функция dfs2 реализует поиск в глубину на обратном графе. 

void dfs2(int v)

{

used[v] = 1;

for (int to : gr[v])

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

}

Основная часть программы. Читаем входные данные. Строим обратный граф.

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

}

Запускаем поиск в глубину на графе из вершины 1.

used.resize(n + 1);

dfs1(1);

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

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

Если вершина i недостижима (used[i] = 0), то путешествие между городами 1 и i невозможно.

if (i <= n)

{

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

return 0;

}

Запускаем поиск в глубину на обратном графе из вершины 1.

used.clear();

used.resize(n + 1);

dfs2(1);

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

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

Если вершина i недостижима (used[i] = 0) из 1 на обратном графе, то путешествие между городами i и 1 невозможно.

if (i <= n)

{

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

return 0;

}

Граф является сильно связным. Выводим сообщение “YES”.

printf("YES\n");