graph_theory_task2

Мамедов Валентин Юрьевич
Группа 17123
---------
Задание: Алгоритм Тарьяна
Выявление блоков/компонент двусвязности графа
=========
Краткое описание кода
=========
На вход сначала подается число n - количество вершин в исходном графе.
Далее вводится матрица смежности графа.

На выходе: блоки компонент двусвязноси графа.

Просмотр кода на Pastebin: https://pastebin.com/v52umRHQ
Тесты программы: https://pastebin.com/ErPJfFd5
========
Мотивация
========
Дан неориентированный граф.

Двусвязные компоненты - максимальные подграфы, такие что при удалении узла, подграф не будет распадаться на части. Эти узлы называются точками сочленения.

Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром.

Блоковый граф — вид неориентированного графа, в котором каждая компонента двусвязности (блок) является кликой.

Таким образом нам нужно найти количество блоков у неориентированного графа.

Для решения этой задачи используем алгоритм Тарьяна, у которого сложность O(n).
========
Описание алгоритма
========
Заднее ребро: это ребро (u, v), такое, что v является предком ребра u, но не является частью дерева DFS.

Поиск компонент реализованы с использованием нерекурсивного поиска в глубину. При посещении вершины она проталкивается во вспомогательный стек, а выталкивается при окончании обработки.

Узел n является точкой сочленения, тогда и только тогда, когда существует поддерево с корнем в n, такое что нет заднего ребра до любого предка n, который ссылается на n в дереве DFS. Отслеживая все пройденные ребра с помощью DFS мы можем получить двусвязные компоненты, потому что все ребра двусвязного графа будут проходить последовательно между точками сочленения.