Найдите массив, к которому принадлежит каждый элемент в заданных запросах, а также количество элементов

Опубликовано: 21 Сентября, 2022

Учитывая массив пар arr[][] длины N и массив запросов[] длины M и целое число R , где каждый запрос содержит целое число от 1 до R , задача для каждого запроса[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 2 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 total number of elements is 3.
For the second query: 4 belongs to the set {4, 5} and the total number of elements is 2.
For the third query: 1 belongs to the set {1, 2, 3} and the total number of elements is 3.
For the fourth query: 3 belongs to the set {1, 2, 3} and the total number of elements is 3.

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

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

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

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ