Программа Python для непересекающихся множеств (или Union-Find) | Набор 1 (обнаружение цикла в неориентированном графе)

Структура данных с непересекающимся набором — это структура данных, которая отслеживает набор элементов, разделенных на несколько непересекающихся (непересекающихся) подмножеств. Алгоритм объединения-поиска — это алгоритм, который выполняет две полезные операции над такой структурой данных:

Найти: определить, в каком подмножестве находится конкретный элемент. Это можно использовать для определения того, находятся ли два элемента в одном и том же подмножестве.

Объединение: объединение двух подмножеств в одно подмножество.

В этом посте мы обсудим применение структуры данных несвязного множества. Приложение должно проверять, содержит ли данный граф цикл или нет.

Алгоритм объединения-поиска можно использовать для проверки того, содержит ли неориентированный граф цикл или нет. Обратите внимание, что мы обсудили алгоритм обнаружения цикла. Это еще один метод, основанный на Union-Find . Этот метод предполагает, что граф не содержит циклов.
Мы можем отслеживать подмножества в одномерном массиве, назовем его parent[].

Рассмотрим следующий график:

Для каждого ребра создайте подмножества, используя обе вершины ребра. Если обе вершины находятся в одном подмножестве, цикл найден.

Изначально все слоты родительского массива инициализируются значением -1 (означает, что в каждом подмножестве есть только один элемент).

0   1   2
-1 -1  -1 

Теперь обработайте все края по одному.

Ребро 0-1: Найдите подмножества, в которых находятся вершины 0 и 1. Поскольку они находятся в разных подмножествах, мы берем их объединение. Для объединения сделайте узел 0 родителем узла 1 или наоборот.

0   1   2    <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})
1  -1  -1

Ребро 1-2: 1 находится в подмножестве 1, а 2 — в подмножестве 2. Итак, возьмем объединение.

0   1   2    <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})
1   2  -1

Ребро 0-2: 0 находится в подмножестве 2, а 2 также находится в подмножестве 2. Следовательно, включение этого ребра образует цикл.

Как подмножество 0 совпадает с 2?
0->1->2 // 1 является родителем 0, а 2 является родителем 1