Поиск космонавтов из разных стран
Имея положительное целое число 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:
- Choose 1 astronaut from country 1 and 1 astronaut from country 2, then the total number of ways is 4*1 = 4.
- Choose 1 astronaut from country 1 and 1 astronaut from country 3, then the total number of ways is 4*1 = 4.
- 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)