Пошаговое представление
1. Выбираем любую вершину из еще не пройденных, обозначим ее как v
2. Запускаем процедуру dfs(v)
- Помечаем вершину v как пройденную
- Для каждой не пройденной смежной с v вершиной (назовем ее to) запускаем dfs(to)
3. Повторяем шаги 1 и 2, пока все вершины не окажутся пройденными
Алгоритм работает за O (N+M)
Применение алгоритма
- Поиск любого пути в графе
- Есть ли путь из вершины S в вершину F
- Связный ли граф
- Сколько компонент связности
- Поиск лексикографически первого пути в графе
- Топологическая сортировка:
Запускаем серию поисков в глубину, чтобы обойти все вершины графа. Отсортируем вершины по времени выхода по убыванию - это и будет ответом. - Задача LCA (наименьший общий предок)
Рассмотрим задачу:
В стране Z есть N городов, которые соединены M дорогами. По дорогам можно ездить в обоих направлениях. Между двумя городами могут существовать несколько дорог, также дорога может вести из города в его же самого. Правительство страны хочет определить количество изолированных друг от друга областей в стране. Область – это набор городов, где между любой парой городов есть путь. Помогите правительству определить это количество.
Формат ввода:
N, M – количество городов и дорог.
Далее следует M строк с описанием дорог. Каждая дорога описывается парой чисел – города которые она соединяет.
Решение:
Решение задачи сводится к нахождению количества компонент связности в графе.
int32_t main() { int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; x--; y--; if (x == y) continue; g[x].insert(y); g[y].insert(x); } int k = 0; for (int i = 0; i < n; ++i) p[i] = 0; for (int i = 0; i < n; ++i) { if (!p[i]){ dfs(i); k++; } } cout << k << endl; return 0; }
- Прочитаем список смежности графа
- Пометим все вершины как не пройденные
- Пройдем по всем вершинам
Если вершина не пройдена
- Запустим dfs от этой вершины
- Увеличим ответ
- Выведем ответ
set < int > g[N]; bool p[N]; void dfs (int v){ if (!p[v]){ p[v] = 1; for (auto to:g[v]){ if (!p[to]) dfs(to); } } }
Сдать задачу:http://dl.gsu.by/tas...=1062969&cid=19
Если ссылка не открывается:
dl.gsu.by Олимпиады по информатике Гомельская гор. 13.10.2012 изолированные города