Почему это работает
- Ребро кладёт оба своих конца в одну группу, а слияние групп ничего не разбивает, поэтому после всех рёбер группа — это ровно вершины, которые достижимы друг из друга.
- Имя группы — её корень. Две вершины в одной группе, когда find даёт им один корень, сколько бы рёбер между ними ни было.
- Сами пути не строим: ответ — одно сравнение двух корней.
Сложность
Время O(n + m · h) для m рёбер, где h — высота деревьев: до n с таким простым find и почти константа, если find перевешивает пройденные вершины прямо на корень, а меньшее дерево подвешивается под большее. Память O(n) на parent.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗