Что такое конденсация графа
Поиск компонент сильной связности: алгоритм Косарайю
На хабре нет ни одной статьи о поиске компонент сильной связности. Однако это интересная задача, имеющая приложения в самых разных сферах: системах рекомендаций, математической логике и, неожиданно, экологии. Ниже формулировка задачи и решение — алгоритм Косарайю.
К делу:
Заметим: отношение сильной связности — это отношение эквивалентности.
Компонентой сильной связности называется класс эквивалентности множества вершин ориентированного графа относительно отношения сильной связности. Другими словами компонента сильной связности = сильно связный подграф. Так как сильная связность — это отношение эквивалентности, то граф разбивается на сильно связные компоненты. Наша задача найти все такие классы эквивалентности.
Пусть дан ориентированный граф G = (V, E). Через G’ = (V, E’) обозначим интертирование G.
Будем обходить граф G в глубину, пока не посетим все вершины. Заведем массив out = [0. |V|-1] — время выхода из вершины. Под временем понимаются логические часы: изначально время равно 0, при переходе в вершину или выходе из неё время увеличивается на 1.
Когда обход закончится, заведем массив vertices, куда добавим все вершины в порядке увеличения времени выхода. Теперь запустим обход в глубинку на инвертированном графе G’. Каждый раз для обхода будем выбирать ещё не посещенную вершину с максимальным индексом в массиве vertices. Все вершины, посещенные в ходе одной итерации dfs, образуют компоненту сильной связности.
Заметим: если граф представлен графом смежности, то нам не требуетcя хранить в памяти инвертированный граф. Иначе нам потребуется O(V+E) доп. памяти. Но, в любом случае, нам требуется O(V) памяти для массивов out и vertices.
Алгоритм состоит из двух обходов DFS. Каждый работает пропорционально V+E для разреженных графов и V^2 для насыщенных. Кроме того, нам требуется O(VlogV) для сортировки вершин при построении массива vertices.
Компоненты сильной связности
Ранее мы научились топологически сортировать ациклические графы. Но в циклических графах тоже иногда требуется найти какую-то структуру, для чего нам нужно ввести понятие сильной связности.
Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.
Граф с тремя компонентами сильной связности
Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.
Часто рассматривают граф, составленный из самих компонент сильной связности, а не индивидуальных вершин. Очевидно, такой граф уже будет ациклическим, и с ним проще работать. Задачу о сжатии каждой компоненты сильной связности в одну вершину называют конденсацией графа, и её решение мы сейчас опишем.
Конденсация графа
Если мы уже знаем, какие вершины лежат в каждой компоненте сильной связности, то построить граф конденсации несложно: нужно провести некоторые манипуляции со списками смежности, заменив для всех ребер номера вершин номерами их компонент, а затем объединив списки смежности для всех вершин каждой компоненты. Поэтому сразу сведем исходную задачу к нахождению самих компонент.
Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.
После того, как мы сделали это с первой вершиной, мы можем пойти по топологически отсортированному списку дальше и делать то же самое с вершинами, для которых компоненту связности мы ещё не отметили.
Сортируем вершины в порядке убывания времени выхода.
Проходимся по массиву вершин в этом порядке, и для ещё непомеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компонентой связности.
После этого номера компонент связности будут топологически отсортированы.
Конденсация графа
Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? В них тоже иногда требуется найти какую-то структуру.
Для этого можно ввести понятие сильной связности.
Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.
Понятно, что такое отношение транзитивно: если \(a\) и \(b\) сильно связны, и \(b\) и \(c\) сильно связны, то \(a\) и \(c\) тоже сильно связны. Поэтому все вершины распадаются на компоненты сильной связности — такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильной связности нет.
Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.
Часто рассматривают граф, составленный из самих компонент сильной связности, а не индивидуальных вершин. Очевидно, такой граф уже будет ациклическим, и с ним проще работать. Задачу о сжатии каждой компоненты сильной связности в одну вершину называют конденсацией графа, и её решение мы сейчас опишем.
Если мы знаем, какие вершины лежат в каждой компоненте сильной связности, то построить граф конденсации несложно: дальше нужно лишь провести некоторые манипуляции со списками смежности. Поэтому сразу сведем исходную задачу к нахождению самих компонент.
Лемма. Запустим dfs. Пусть \(A\) и \(B\) — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро \(A \to B\). Тогда\[ \max\limits_(tout_a) > \max\limits_
Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.
Пусть первой была достигнута компонента \(A\), то есть в какой-то момент времени dfs заходит в некоторую вершину \(v\) компоненты \(A\), и при этом все остальные вершины компонент \(A\) и \(B\) ещё не посещены. Но так как по условию в графе конденсаций есть ребро \(A \to B\), то из вершины \(v\) будет достижима не только вся компонента \(A\), но и вся компонента \(B\). Это означает, что при запуске из вершины \(v\) обход в глубину пройдёт по всем вершинам компонент \(A\) и \(B\), а, значит, они станут потомками по отношению к \(v\) в дереве обхода, и для любой вершины \(u \in A \cup B, u \ne v\) будет выполнено \(tout_v] > tout_u\), что и утверждалось.
Второй случай проще: из \(B\) по условию нельзя дойти до \(A\), а значит, если первой была достигнута \(B\), то dfs выйдет из всех её вершин ещё до того, как войти в \(A\).
После того, как мы сделали это с первой вершиной, мы можем пойти по топологически отсортированному списку дальше и делать то же самое с вершинами, для которых компоненту связности мы ещё не отметили.
После этого номера компонент связности будут топологически отсортированы.
Что такое конденсация графа
Такое отношение на вершинах разбивает все множество вершин на непересекающиеся подмножества связанных вершин, называемые компонентами сильной связности (strongly connected components). Граф на рис. 1 имеет пять таких компонент.
а. 
б. Рис 1. (а) Ориентированный граф и его компоненты сильной связности. (б) Конденсация ориентированного графа.
Стянем теперь каждую компоненту сильной связности в отдельную вершину (метавершину) и оставим только ребра между метавершинами (см. рис. 1), удалив дубликаты. Полученный граф называется метаграфом (meta-graph) (также графом компонент или конденсацией) исходного. Он не содержит циклов: если бы несколько компонент образовывали цикл, то вершины этих компонент были бы в исходном графе достижимы друг из друга и вошли бы в одну компоненту.
Свойство 0. Граф конденсации любого ориентированного графа является ациклическим (и может быть топологически упорядочен).
Но как построить конденсацию для данного графа? Компоненты сильной связности и метаграф могут быть построены за линейное время. Начнем с такого замечания, которое уже было доказано в предыдущих лекциях.
Значит, если вызвать Explore для вершины, которая лежит в компоненте-стоке, то мы обойдем как раз все вершины этой компоненты. Например, граф рис. 1 имеет две такие компоненты, и вызов Explore для вершины K обойдет бОльшую из них.
Остается понять, (а) как найти вершину, которая гарантированно лежит в компоненте-стоке, и (б) что делать после нахождения компоненты-стока.
Для начала ответим на первый вопрос. Сначала покажем, как решать симметричную задачу: найти вершину в компоненте-истоке
Заметим, что явно удалять вершины не нужно. Достаточно просто обойти вершины в порядке убывания tout и вызвать Explore из каждой непосещённой.
Итак, мы построили следующий алгоритм выделения компонент сильной связности:
Данный алгоритм не просто находит все компоненты связности, но и строит ациклический граф конденсации в порядке топологической сортировки компонент.
Что такое конденсация графа
A. Топологическая сортировка
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.
В первой строке входного файла даны два натуральных числа N и M (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000) — количество вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дан неориентированный граф, не обязательно связный, но не содержащий петель и кратных рёбер. Требуется найти все мосты в нём.
Первая строка входного файла содержит два натуральных числа n и m — количества вершин и рёбер графа соответственно (1 ≤ n ≤ 20 000, 1 ≤ m ≤ 200 000).
Следующие m строк содержат описание рёбер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).
Первая строка выходного файла должна содержать одно натуральное число b — количество мостов в заданном графе. На следующей строке выведите b целых чисел — номера рёбер, которые являются мостами, в возрастающем порядке. Рёбра нумеруются с единицы в том порядке, в котором они заданы во входном файле.
входные данные
выходные данные
C. Точки сочленения
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дан неориентированный граф. Требуется найти все точки сочленения в нём.
Первая строка входного файла содержит два натуральных числа n и m — количества вершин и рёбер графа соответственно (1 ≤ n ≤ 20 000, 1 ≤ m ≤ 200 000).
Следующие m строк содержат описание рёбер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).
Первая строка выходного файла должна содержать одно натуральное число b — количество точек сочленения в заданном графе. На следующей строке выведите b целых чисел — номера вершин, которые являются точками сочленения, в возрастающем порядке.
входные данные
выходные данные
D. Компоненты реберной двусвязности
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
Компонентой реберной двусвязности графа 〈 V,E 〉 называется подмножество вершин S ⊂ V, такое что для любых различных u и v из этого множества существует не менее двух реберно не пересекающихся путей из u в v.
Дан неориентированный граф. Требуется выделить компоненты реберной двусвязности в нем.
Первая строка входного файла содержит два натуральных числа n и m — количества вершин и ребер графа соответственно (1 ≤ n ≤ 20 000, 1 ≤ m ≤ 200 000).
Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).
входные данные
выходные данные
E. Компоненты вершинной двусвязности
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
Компонентой вершинной двусвязности графа 〈 V,E 〉 называется максимальный по включению подграф (состоящий из вершин и ребер), такой что любые два ребра из него лежат на вершинно простом цикле.
Дан неориентированный граф без петель. Требуется выделить компоненты вершинной двусвязности в нем.
Первая строка входного файла содержит два натуральных числа n и m — количества вершин и ребер графа соответственно (1 ≤ n ≤ 20 000, 1 ≤ m ≤ 200 000).
Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — номерами концов ребра (1 ≤ bi, ei ≤ n).
входные данные
выходные данные
F. Конденсация графа
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Требуется найти количество ребер в конденсации ориентированного графа. Примечание: конденсация графа не содержит кратных ребер.
Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно (n ≤ 10 000, m ≤ 100 000). Следующие m строк содержат описание ребер, по одному на строке. Ребро номер i описывается двумя натуральными числами bi, ei — началом и концом ребра соответственно (1 ≤ bi, ei ≤ n). В графе могут присутствовать кратные ребра и петли.
Единственная строка выходного файла должна содержать одно число — количество ребер в конденсации графа.
входные данные
выходные данные
G. Планирование вечеринки
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Петя планирует вечеринку, это дело непростое. Одна из главных проблем в том, что некоторые его друзья плохо ладят друг с другом, а некоторые — наоборот. В результате у него есть множество требований, например: «Я приду только если придет Гена» или «Если там будет Марина, то меня там точно не будет».
Помогите Пете составить хоть какой-нибудь список гостей, удовлетворяющий всем свойствам, или скажите, что это невозможно
В первой строке входного файла записаны числа n и m — число друзей Пети и число условий (1 ≤ n, m ≤ 1000). В следующих n строках записаны имена друзей. Имена друзей состоят из маленьких латинских букв и имеют длину не больше 10. В следующих m строках записаны условия.
Выведите в первой строке число k — число друзей, которых нужно пригласить. В следующих k строках выведите их имена.
входные данные
выходные данные
входные данные
выходные данные
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: avia.in
вывод: avia.out
Главного конструктора Петю попросили разработать новую модель самолета для компании «Air Бубундия». Оказалось, что самая сложная часть заключается в подборе оптимального размера топливного бака.
Главный картограф «Air Бубундия» Вася составил подробную карту Бубундии. На этой карте он отметил расход топлива для перелета между каждой парой городов.
Петя хочет сделать размер бака минимально возможным, для которого самолет сможет долететь от любого города в любой другой (возможно, с дозаправками в пути).
Первая строка входного файла содержит натуральное число n (1 ≤ n ≤ 1000) — число городов в Бубундии.
Далее идут n строк по n чисел каждая. j-ое число в i-ой строке равно расходу топлива при перелете из i-ого города в j-ый. Все числа не меньше нуля и меньше 10^9. Гарантируется, что для любого i в i-ой строчке i-ое число равно нулю.
Первая строка выходного файла должна содержать одно число — оптимальный размер бака.