Как можно использовать структуры данных Union / Find для алгоритма Крускала?

Question

http://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

Объединение / Поиск структуры данных, используемой для непересекающихся множеств ...

Answer 1

Это указано в записи для алгоритма Крускала, но вы можете использовать структуру union / find для проверки (через FIND), соединяет ли ребро два разных дерева или образует ли он цикл при добавлении.

Та же самая структура может быть обновлена ​​(через UNION), если ребро не образует цикл и добавлено в связующее дерево.