Поиск космонавтов из разных стран

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

Имея положительное целое число N , обозначающее количество астронавтов (обозначенное от 0 до (N – 1) ) и матрицу mat[][] , содержащую пары астронавтов из одной страны, задача состоит в том, чтобы подсчитать количество способов выбрать двух космонавтов из разных стран.

Примеры:

Input: N = 6, mat[][] = {{0, 1}, {0, 2}, {2, 5}}
Output: 9
Explanation:
Astronauts with ID {0, 1, 2, 5} belong to first country, astronaut with ID {3} belongs to second country and astronaut with ID {4} belongs to third country. The number of ways to choose two astronauts from different countries is:

  1. Choose 1 astronaut from country 1 and 1 astronaut from country 2, then the total number of ways is 4*1 = 4.
  2. Choose 1 astronaut from country 1 and 1 astronaut from country 3, then the total number of ways is 4*1 = 4.
  3. Choose 1 astronaut from country 2 and 1 astronaut from country 3, then the total number of ways is 1*1 = 1.

Therefore, the total number of ways is 4 + 4 + 1 = 9. 

Input: N = 5, mat[][] = {{0, 1}, {2, 3}, {0, 4}}
Output: 6

Подход: данная проблема может быть решена путем моделирования этой проблемы в виде графа, в котором астронавты представляют вершины графа, а данные пары представляют ребра в графе. После построения графа нужно подсчитать количество способов выбрать двух космонавтов из разных стран. Следуйте инструкциям, чтобы решить проблему:

  • Создайте список списков, adj[][] для хранения списка смежности графа.
  • Пройдите по заданному массиву arr[] с помощью переменной i и добавьте arr[i][1] к adj[arr[i][0]] , а также добавьте arr[i][0] к adj[arr[i][1] ]] для неориентированного ребра.
  • Теперь найдите размер каждого связанного компонента графа, выполнив поиск в глубину, используя подход, обсуждаемый в этой статье, и сохраните все размеры связанных компонентов в массиве, скажем, v[] .
  • Инициализируйте целочисленную переменную, скажем , как общее количество способов выбрать 2 астронавтов из N астронавтов, т. е. N*(N – 1)/2 .
  • Пройдите массив v[] и вычтите v[i]*(v[i] – 1)/2 из переменной ans , чтобы исключить все возможные пары среди всех связанных компонентов.
  • После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

Временная сложность: O(N + E), где N — количество вершин, а E — количество ребер.
Вспомогательное пространство: O(N + E)

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