Решите, существует ли MST, который содержит данное ребро в линейном времени

Пусть G = (V, E) — взвешенный, связный и неориентированный граф, а e — любое ребро в E. Покажите линейный алгоритм, определяющий, существует ли минимальное остовное дерево, содержащее ребро e.

Мне удалось найти странное «решение» вопроса 1, и оно, кажется, работает, но я не думаю, что оно линейно:

Они предложили использовать union find и выполнить Union(u,v) для каждого ребра (u,v), такого что W(u,v) ‹ W(e). Теперь предположим, что e = (x, y). Теперь, если find(x) != find(y), то x и y не связаны, и W(e) определенно будет следующим весом, который будет проверен алгоритмом Крускала, поэтому наверняка существует MST, который содержит ребро е.

С другой стороны, если find(x) = find(y), то если бы мы запустили алгоритм Крускала до этой точки, x и y наверняка были бы соединены, поэтому мы не можем добавить ребро e ни к одному MST (и известно, что, манипулируя отсортированный порядок ребер, имеющих одинаковый вес - алгоритм Крускала можно использовать для создания любого MST).

Я не понимаю, почему это линейно? Разве это не должно стоить O( |E| alpha(|V|)) ) из-за союзов?

Возможно, есть другой способ сделать это за линейное время?

заранее спасибо