Построить график по размеру компонентов для каждого узла

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

Учитывая массив A[] размера N для каждого индекса i в диапазоне [0, N) значение A[i] обозначает размер связанного компонента узла i . Задача состоит в том, чтобы найти ребра возможного графа, иначе выведите -1.

Note: There may be more than 1 possible answers for each array. Print any one of them. 

Примеры:

Input: N = 5, A[] = {2, 1, 1, 2, 1}
Output: {{0, 3}}
Explanation: The size of Connected Components of nodes (0, 3) is 2, every other node is singular.

Input: N = 4, A[] = {2, 2, 2, 2}
Output: {{0, 1}, {2, 3}}
Explanation: Other possible variations are – {{0, 2}, {1, 3}}, {{0, 3}, {1, 2}}

Input: N=2, A[] = {1, 1}
Output: Graph is already connected.
Explanation: Since, each connected component size is 1, no edge is needed to connect any pair of nodes.

Подход: Идея состоит в том, чтобы наблюдать, что все одинаковые размеры компонентов могут быть связаны друг с другом, используя общее количество узлов, равное размеру значения массива. Итак, сохраните все узлы с одинаковым значением индекса на карте. Значения узлов могут храниться в структуре карты map<int, vector<int>>. Проверьте для каждого размера подключенного компонента, что соответствующие общие узлы кратны размеру. Если для любого компонента связности вышеуказанное условие не выполняется, то корректного графа не будет. Немедленно верните -1 . В противном случае для всех множественных сохраняйте вершины и соединяйте их смежно. Сохраните все ребра в массиве и выведите результат. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте флаг логической переменной как false , чтобы проверить, равны ли все значения 1. Если это так, то нет необходимости формировать какое-либо ребро.
  • Инициализируйте карту вектора mp[] для хранения индексов для определенного размера связанного компонента.
  • Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
    • Вставьте значение i в вектор на карте в точке A[i].
    • Если A[i] не равно 1, то установить значение флага как true .
  • Если флаг ложный, то вернуться.
  • Переберите карту, используя переменную x , и выполните следующие задачи:
    • Если x.second.size() не делится на x.first, тогда выведите -1 и верните 0 .
  • Инициализируйте вектор пары int edge[] для хранения ребер.
  • Переберите карту, используя переменную x , и выполните следующие задачи:
    • Инициализировать векторные узлы [] как вектор в текущей позиции.
    • Повторяйте цикл while, пока размер узлов [] не станет больше 0 , и выполните следующие задачи:
      • Инициализируйте переменную cnt как 0.
      • Инициализировать вектор component_nodes[].
      • Повторяйте цикл while до тех пор, пока cnt не станет равным x.first, и выполните следующие задачи:
        • Поместите значение lat в векторных узлах [] в векторный компонент component_nodes [] и извлеките это значение из узлов [] и увеличьте значение cnt на 1.
      • Перебрать диапазон [1, component_nodes.size()) с помощью переменной i и выполнить следующие задачи:
        • Вставьте пару {component_nodes[i], component_nodes[i-1]} в ребра вектора[] .
  • После выполнения вышеуказанных шагов выведите в качестве ответа вектор ребер[] .

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

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

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