Time and Space Complexity

Временная сложность:

• Сортировка E ребер занимает O(E log E); каждая операция union-find выполняется почти за O(1) с использованием сжатия путей, поэтому классический алгоритм Краскала имеет сложность O(E log E). Версия с выбором минимума, которую мы строим здесь, имеет сложность O(E²), что допустимо для небольших графов.

Пространственная сложность:

• O(V) для массива parent (плюс входные ребра).

Резюме:

• Алгоритм Краскала строит MST, добавляя на каждом шаге самое дешевое ребро, не образующее цикл, используя union-find для проверки циклов.
• Все MST имеют одинаковый общий вес, поэтому ответ уникален.