Минимизируйте стоимость соединения графа, соединяя любые пары вершин, стоимость которых не меньше 0.

Для заданного несвязного графа G с N вершинами и M ребрами и массива cost[] , соответствующего каждой вершине, задача состоит в том, чтобы найти минимальную стоимость построения графа путем соединения любых пар вершин, имеющих стоимость вершин не менее 0 , и стоимость соединения этих пар вершин равна сумме стоимости отдельных вершин. Если это невозможно, то выведите «-1» .

Примеры:

Input: N = 6, G[] = {{3, 1}, {2, 3}, {2, 1}, {4, 5}, {5, 6}, {6, 4}}, cost[] = {2, 1, 5, 3, 2, 9}
Output: 3
Explanation: The initial graph has two connected components – {1, 2, 3} and {4, 5, 6}. We can add an edge between 2 to 5 at a cost of cost[2] + cost[5] = 1 + 2 = 3. After adding this edge, the whole graph is connected.

Input: N = 6, G[] = {{3, 1}, {2, 3}, {2, 1}, {4, 5}, {5, 6}, {6, 4}}, cost[] = {2, 1, 5, -3, -2, -9}
Output: -1
Explanation: It is not possible to make the graph connected

Подход: Данная задача может быть решена с использованием структуры данных Disjoint Set Union. Идея состоит в том, чтобы сохранить все минимальные значения, которые больше или равны 0 , скажем, minVal[] для всех различных подключенных компонентов, и проверить, меньше ли какое-либо значение в minVal[] нуля, если оно верно , затем вывести -1 , В противном случае найдите минимальное значение в minVal[] , скажем min , и найдите сумму всех минимальных значений с минимальным значением и выведите ответ.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте вектор minVal[] , чтобы найти минимальный элемент каждого набора.
• Инициализируйте векторы parent(N+1), rank(N+1, 0), minVal(N+1) .
• Инициализируйте набор, скажем, s , чтобы сохранить родителя каждого набора.
• Инициализируйте переменную, скажем, minCost , которая хранит минимальную стоимость.
• Переберите диапазон [1, N+1), используя переменную i , и установите значение parent[i] как I и minVal[i] как cost[i – 1] .
• Перебрать вектор G , используя переменную i , и вызвать функциональную операцию Union(parent, rank, minVal, i.first, i.second) .
• Переберите диапазон [1, N+1), используя переменную i , и вставьте родительский элемент I в s .
• Переберите набор s и найдите минимальное значение s , сохраните его в min и отметьте флаг как истинный, если какое-либо значение отрицательное.
• Если данный граф уже связан или значение флага ложно , то:
  • Переберите s , используя переменную I , и если минимальное значение не равно I , обновите значение minCost до minCost += (minVal[i] + min.second) .
  • После выполнения вышеуказанного шага выведите значение minCost как результирующую минимальную стоимость.
• В противном случае выведите -1 .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*log M)
Вспомогательное пространство: O(N)