Наименьшая вершина в компонентах связности всех вершин данного непрямого графа

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

Для заданного неориентированного графа G(V, E), состоящего из 2 N вершин и M ребер, задача состоит в том, чтобы найти наименьшую вершину в компоненте связности вершины i для всех значений i в диапазоне [1, N] .

Примеры:

Input: N = 5, edges[] = {{1, 2}, {2, 3}, {4, 5}}
Output: 1 1 1 4 4
Explanation: The given graph can be divided into a set of two connected components, i.e, {1, 2, 3} and {4, 5}.

  1. For i = 1, vertex 1 belongs to the component {1, 2, 3}. Therefore, the minimum vertex in the set is 1.
  2. For i = 2, vertex 2 belongs to the component {1, 2, 3}. Therefore, the minimum vertex in the set is 1.
  3. For i = 3, vertex 3 belongs to the component {1, 2, 3}. Therefore, the minimum vertex in the set is 1.
  4. For i = 4, vertex 4 belongs to the component {4, 5}. Therefore, the minimum vertex in the set is 4.
  5. For i = 5, vertex 5 belongs to the component {4, 5}. Therefore, the minimum vertex in the set is 4.

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

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

  • Реализуйте функцию find_set и union_set объединения непересекающихся множеств, используя подход, обсуждаемый в этой статье, где find_set(x) возвращает номер набора, содержащий x , а union_set(x, y) объединяет набор, содержащий x , с набором, содержащим y .
  • Пройдите по заданному массиву edge [] и для каждого ребра (u, v) объедините множество, содержащее u , с множеством, содержащим v .
  • Создайте неупорядоченную карту minVal , где minVal[x] хранит минимальную вершину набора, содержащего x в качестве элемента.
  • Переберите все вершины, используя переменную i , и для каждой вершины установите значение minVal[find_set(node i)] равным минимуму minVal[find_set(i)] и i .
  • После выполнения вышеуказанных шагов для каждой вершины i в диапазоне [1, N] выведите в качестве результата значение minVal[find_set(i)] .

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

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

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