Union-Find (СНМ)

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

P19 Union-Find (СНМ)1×

Пример задачи: 5 компьютеров, 0–4, соединены кабелями 0–1, 2–1, 0–2. Сколько получилось отдельных сетей? Ответ: 3 — {0, 1, 2}, {3} и {4}.

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

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

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
11
12function find(x):
13 while parent[x] is not x:
14 x = parent[x]
15 return x
состояние
parent
[0, 1, 2, 3, 4]
groups
–
a
–
b
–
rootA
–
rootB
–
x
–
историянажмите шаг, чтобы вернуться

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

Как узнать

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

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

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

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

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