Union-Find (СНМ)

Каждая группа — дерево, а её имя — корень. Чтобы узнать, в одной ли группе два элемента, сравниваем их корни, а чтобы слить группы, подвешиваем один корень к другому. Ничего не перекрашиваем и не пересчитываем.

P19 Union-Find (СНМ)1×

Пример задачи: посчитать связные группы после списка соединений.

смотрим сейчаскорень группы

Каждый элемент — сам себе корень

parent = [0, 1, 2, 3, 4]groups = –a = –b = –rootA = –rootB = –x = –

01/41

сначала · назад · пуск · шаг

Скорость

1function countGroups(n, connections):

2 parent = [0, 1, ..., n - 1]

3 groups = n

4 for (a, b) in connections:

5 rootA = find(a)

6 rootB = find(b)

7 if rootA is not rootB:

8 parent[rootB] = rootA

9 groups = groups - 1

10 return groups

12function find(x):

13 while parent[x] is not x:

14 x = parent[x]

15 return x

← → шаг · пробел — пауза

Как узнать

элементы, которые только соединяются и никогда не разъединяются, и вопросы вроде «сколько групп?», «связаны ли a и b?» или «какое ребро замыкает цикл?».

Как решать такие задачи

Сделай каждый элемент отдельной группой: parent[x] = x.
Напиши find(x): иди по parent, пока не дойдёшь до элемента, который сам себе родитель. Это корень.
Чтобы соединить a и b, найди оба корня. Если они разные, сделай один корень родителем другого и уменьши число групп на одну.
Держи деревья плоскими: в find перевешивай каждый пройденный узел прямо на корень, а меньшее дерево подвешивай под большее.

Где встречается

Поиск объектов на картинке. OpenCV (connectedComponents) и SciPy (ndimage.label) находят связные пятна пикселей: соседние пиксели объединяют в одну группу, а потом каждой группе дают номер.
Разбиение фото на области. Алгоритм Фельценшвальба, который есть в scikit-image, сливает соседние пиксели в области, если они похожи, и хранит области в Union-Find.