Максимальный элемент в компоненте связности данного узла для Q запросов

Дан массив пар arr[][] длины N и массив запросов[] длины M и целое число R , где запросы[i] содержат целое число от 1 до R , задача для каждого запроса[i] заключается в том, чтобы найти максимальный элемент связных компонентов узла со значением query[i] .

Note: Initially every integer from 1 to R belongs to the distinct set.

Примеры:

Input: R = 5, arr = {{1, 2}, {2, 3}, {4, 5}}, queries[] = {2, 4, 1, 3}
Output: 3 5 3 3
Explanation: After making the sets from the arr[] pairs, {1, 2, 3}, {4, 5}
For the first query: 2 belongs to the set {1, 2, 3} and the maximum element is 3
For the second query: 4 belongs to the set {4, 5} and the maximum element is 5
For the third query: 1 belongs to the set {1, 2, 3} and the maximum element is 3
For the fourth query: 3 belongs to the set {1, 2, 3} and the maximum element is 3

Input: R = 6, arr = {{1, 3}, {2, 4}}, queries = {2, 5, 6, 1}
Output: 4 5 6 3

Подход: Данная задача может быть решена с помощью объединения непересекающихся множеств. Изначально все элементы находятся в разных наборах, обрабатывают arr[] и выполняют операцию объединения для заданных пар и в объединении обновляют максимальное значение для каждого набора в массиве, скажем, значение maxValue[] для родительского элемента. Для каждого запроса выполните операцию поиска и для возвращенного родительского элемента найдите maxParent[parent] . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте вектор maxValue[] , чтобы найти максимальный элемент каждого набора.
• Инициализируйте векторы parent(R+1), rank(R+1, 0), maxValue(R+1) .
• Переберите диапазон [1, R+1), используя переменную i , и установите значение parent[i] и maxValue[i] как i .
• Перебрать диапазон [1, N-1], используя переменную i , и вызвать функциональную операцию Union(parent, rank, maxValue, arr[i].first, arr[i].second) .
• Переберите диапазон [1, M-1], используя переменную i , и выполните следующие шаги:
  • вызов операции функции Find(parent, query[i]) .
  • Выведите значение maxValue[i] в качестве результирующего максимального элемента.

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

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