Что вы не поняли в решении: вы оптимизируете «чёрную» половинку графа, забыв, что самое малое ребро может быть в «белой».
ДЛЯ КАЖДОЙ ВЕРШИНЫ: ук-ль на «начальника» + флаг инверсии. Если у вершины нет начальника — то указывает в null.
ДИРЕКТОРОМ назовём вершину, у которого нет начальников. Считаем также, что у директора флаг инверсии всегда false.
Заведём функцию getInfoNonDestructive, она возвращает структуру из двух элементов. Во-первых, это директор (никогда не null!!). Во-вторых, это цвет — XOR флагов инверсии от самóй вершины до директора.
Функция getInfo вызовет getInfoNonDestructive, а затем проведёт ОПТИМИЗАЦИЮ СТРУКТУРЫ: ЕСЛИ вершина имеет начальника, ТО: начальник вершины := директор, флаг инверсии вершины := цвет вершины.
СЛИЯНИЕ фирм происходит так. Директор фирмы становится подчинённым кому-то из членов другой фирмы.
ИЗНАЧАЛЬНО для всех вершин начальник — null, флаг инверсии — false. То есть каждая вершина белая и сама себе директор.
РЕШЕНИЕ: Отсортируем рёбра в порядке возрастания.
Для каждого ребра…
• Находим информацию о вершинах — концах ребра.
• Если директор один и цвета разные — ничего не делаем.
• Если директор один и цвет один — выводим вес этого ребра как ответ.
• Если директора разные — сливаем фирмы. Подкручиваем флаг инверсии того директора, который исчез, так, чтобы цвета вершин — концов ребра были разные. Хотя бы так.
VertexInfo info1 = getInfo(vertex1);
VertexInfo info2 = getInfo(vertex2);
if (…) {
info1.director->superior = info2.director;
VertexInfo info1new = getInfoNonDestructive(vertex1);
if (info1new.color == info2.color)
info1.director->inverseFlag = !info1.director->inverseFlag;
}
ВНИМАНИЕ, без оптимизации структуры сложность с «чуть более O(N)» превращается в N²! Но конкретно в этом месте важно получить инфу без разрушений — временно запрещается кого бы то ни было выводить из-под старого директора, пока не выставим ему флаг инверсии цвета.
Если рёбер не осталось — перед нами двудольный граф, такого по условию не бывает.
(такая структура данных, только без флага инверсии, называется, «система непересекающихся множеств»).
ТЕОРИЯ. Начиная от самых «маленьких» рёбер, начинаем раскрашивать вершины в разные цвета. Если в какой-то момент это не удалось (цвета уже одинаковые) — выводим это ребро как ответ. Если соединяются два раскрашенных «островка» (в нашей терминологии «фирмы») — возможно, один из островков придётся инвертировать, и надо наладить инверсию так, чтобы она не захватила весь островок (судя по цифре 10
5, от нас ожидают сложность N log N, а не N²). Поскольку соединение кусков графа рёбрами и подсчёт компонент связности — это самая настоящая система непересекающихся множеств, я попытался приделать к этой самой СнПМ раскраску, не повышающую общую сложность (амортизированные почти что O(1) за транзакцию).
Попробуй доказать самостоятельно, что данная система не зависит от того, в каком порядке оказались рёбра с одинаковым весом.
И кончайте на чужом буе в рай въезжать!