Определите, является ли граф двудольным, используя объединение find (иначе говоря, непересекающиеся множества)

Question

Я делаю задачу на Spoj, которая в основном сводится к обнаружению двудольного графа. Я пытаюсь просто раскрасить график, используя dfs, но он слишком медленный. Некоторые парни комментируют это

Нет бфс, нет бф, нет бипартийного графа. Простой Union-Find Set сделает это (действительно, со скоростью). Подсказка № 1: Цикл четной длины не влияет на делимость на 2 (вау, так много я в слове) длины путей между двумя узлами. Подсказка № 2: (СПОЙЛЕР) пусть dist [i] будет расстоянием пути от i до parent [i]. обновите его с помощью функции поиска и объединения. Это может быть улучшено для создания массива dist. Bool.

Может ли кто-нибудь объяснить, что он имеет в виду? Я думаю, что он пытается сказать, что для каждого узла вы сохраняете расстояние между узлом и представительным элементом. Затем, если вы попытаетесь объединить два узла в одном наборе, и если они имеют одинаковую четность, то вы создадите нечетный цикл, поэтому график не может быть двудольным. Однако я не понимаю, как это будет реализовано. Как можно объединить два набора при учете расстояния? Разве вам не нужно просматривать весь набор, чтобы найти все элементы для обновления?

Ссылка на проблему: https://www.spoj.com/problems/BUGLIFE/

Answer 1

Учитывая график, представленный в виде списка смежности (то есть списка ребер), вы можете определить, является ли он двудольным следующим образом:

• Инициализировать структуру данных с несвязным множеством SETS , с единичным набором для каждой вершины. (Если между двумя вершинами есть путь равной длины, то мы в конечном итоге объединим эти две вершины в один и тот же набор, если только мы не вернем ꜰᴀʟꜱᴇ первым.)
• Инициализировать отображение MAP от каждой вершины до ɴɪʟ. (При рассмотрении ребер мы будем заполнять MAP отображением каждой вершины на одного из ее соседей.)
• Для каждого ребра { u , v }:
  • Если u и v принадлежат одному и тому же набору в SETS , верните ꜰᴀʟꜱᴇ.
  • Если MAP [ u ] = ɴɪʟ, установите MAP [ u ]: = v .
    В противном случае обновите SETS , чтобы объединить v с MAP [ u ].
  • Если MAP [ v ] = ɴɪʟ, установите MAP [ v ]: = u .
    В противном случае обновите SETS , чтобы объединить u с MAP [ v ].
• Возврат ᴛʀᴜᴇ.