Modern C Challenge 4

от тебя требуют реализовать стандартную структуру данных «система непересекающихся множеств с эвристикой сжатия путей».

Откуда это? Книга? Можно название?

Modern C Полировка знаний о Си (комментарий)

Спасибо.

Грубо говоря:

size_t parent[100500];
parent[i] = SIZE_MAX;

FindReplace должна пройти по цепочке parent[x], parent[parent[x]], … и обновить каждый посещённый элемент. Если что, структура Union-Find описана много где.

укустивать оба дерева и прививать одно(желательно меньшее - а тут засада по высоте либо по числу и тут засада по листьям либо по общему узлов) к другому

самая эфективная и лаконичная прежде чем найти корни (ака вершина указующая на себя) ужатие и подсчёт( с точностью +-) и переплетениe LOL

while a!=p[a]

a=p[a]=p[p[a]]

findreplace(ф) - НАЙТИкорень(ф)ЗАМЕНИТЬродителей(на пути от ф до корня на сам корень

ps

• либо вторым проходом либо на обратном ходе по стеку - либо на обратном проходе но вместо рекурскии(стека) использую переписывание на массиве - например при проходе в корень заменяя вместо родителя потомка :) )

либо (Ага-идея) - при первом же проходе пока идём до корня и включая его записываем во всю эту ветвь например исходный лист А - т.е из дерева с корнем в r делаем дерево с одуванчиком вершин на старом пути из А в r смотрящим на А

оно конечно подращивает все остальные пути в r на +1 в А но если это делается при слияние двух деревьев это менее убыточно чем просто перестройка корня :)