В алгоритме Краскала компоненты связности удобно обозначать числами, а для каждой вершины писать, к какой компоненте связности она относится. Таким образом, данная задача представляет собой перепометку компонент связности после добавления очередного ребра.