Самый ранний момент, когда все становятся друзьями

Дана группа из N человек, каждый из которых имеет уникальное значение идентификатора от 0 до (N – 1) , и массив arr[] из M элементов вида {U, V, время} , представляющий, что человек U познакомится с человеком V в указанное время . Предположим, что человек U знаком с человеком V , если U дружит с V или если U дружит с кем-то, кто знаком с V. Задача состоит в том, чтобы найти самое раннее время, когда каждый человек познакомился друг с другом.

Примеры:

Input: N = 4, arr[] = {{0, 1, 2}, {1, 2, 3}, {2, 3, 4}}
Output: 4
Explanation: Initially, the number of people are 4, i.e, {0}, {1}, {2}, {3}. 

• At time = 2, {0} and {1} became friends. Therefore, the group of acquainted people becomes {0, 1}, {2}, {3}.
• At time = 3, {1} and {2} became friends. Therefore, the group of acquainted people becomes {0, 1, 2}, {3}.
• At time = 4, {2} and {3} became friends. Therefore, the group of acquainted people becomes {0, 1, 2, 3}.

Hence, at time = 4, every person became acquainted with each other.

Input: N = 6, arr[] = {{0, 1, 4}, {3, 4, 5}, {2, 3, 14}, {1, 5, 24}, {2, 4, 12}, {0, 3, 42}, {1, 2, 41}, {4, 5, 11}}
Output: 24

Подход: данная проблема может быть решена с использованием структуры данных объединения непересекающихся множеств. Идея состоит в том, чтобы выполнять операции объединения между людьми в порядке возрастания ценности времени. Искомым ответом будет время, когда все люди принадлежат к одному множеству. Выполните следующие шаги, чтобы решить данную проблему:

• Реализуйте структуру данных Disjoint Set Union с функциями union и findSet в соответствии с обсуждаемым здесь алгоритмом.
• Инициализируйте переменную time , в которой хранится значение текущей метки времени DSU.
• Отсортируйте данный массив arr[] в порядке возрастания времени.
• Пройдите по заданному массиву arr[] с помощью переменной i и выполните операцию объединения между (U _i , Vi _i ) и обновите текущую метку времени до времени _i если U _i и V _i принадлежат разным множествам.
• Если общее количество наборов после полного обхода массива arr[] равно 1 , вернуть значение переменной time , иначе вернуть -1 .

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

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