Construya un gráfico a partir del tamaño de los componentes para cada Node

Dada una array A[] de tamaño N , para cada índice i en el rango [0, N) el valor A[i] denota el tamaño del componente conectado del Node i . La tarea es encontrar los bordes para el posible gráfico , sino imprime -1.

Nota: Puede haber más de 1 respuesta posible para cada array. Imprime cualquiera de ellos. 

Ejemplos:

Entrada: N = 5, A[] = {2, 1, 1, 2, 1}
Salida: {{0, 3}}
Explicación: El tamaño de los componentes conectados de los Nodes (0, 3) es 2, cada dos Nodes es singular.

Entrada: N = 4, A[] = {2, 2, 2, 2}
Salida: {{0, 1}, {2, 3}}
Explicación: Otras variaciones posibles son: {{0, 2}, {1 , 3}}, {{0, 3}, {1, 2}}

Entrada: N=2, A[] = {1, 1}
Salida: El gráfico ya está conectado.
Explicación: dado que el tamaño de cada componente conectado es 1, no se necesita ningún borde para conectar ningún par de Nodes.

Enfoque: La idea es observar que todos los tamaños de componentes iguales se pueden conectar entre sí usando Nodes totales iguales al tamaño del valor de la array. Por lo tanto, almacene todos los Nodes con el mismo valor de índice en un mapa . Los valores de los Nodes se pueden almacenar con una estructura de mapa map<int, vector<int>> . Verifique para cada tamaño de componente conectado que los Nodes totales correspondientes sean un múltiplo del tamaño. Si para cualquier componente conectado la condición anterior falla, no habrá un gráfico válido. Devuelve -1 inmediatamente. De lo contrario, para todas las tiendas múltiples, los vértices y los conectan de forma adyacente. Almacene todos los bordes en una array y emita el resultado. Siga los pasos a continuación para resolver el problema:

• Inicialice un indicador de variable booleana como falso para verificar si todos los valores son 1. Si es así, entonces no hay necesidad de formar ningún borde.
• Inicialice un mapa del vector mp[] para almacenar los índices para un tamaño de componente conectado particular.
• Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
  • Introduzca el valor i en el vector del mapa en A[i].
  • Si A[i] no es igual a 1, establezca el valor de la bandera como verdadero .
• Si la bandera es falsa, entonces regresa.
• Iterar sobre el mapa usando la variable x y realizar las siguientes tareas:
  • Si x.second.size() no es divisible por x.first, imprima -1 y devuelva 0 .
• Inicialice un vector de par de bordes int [] para almacenar los bordes.
• Iterar sobre el mapa usando la variable x y realizar las siguientes tareas:
  • Inicializa un vector nodes[] como el vector en la posición actual.
  • Iterar en un ciclo while hasta que el tamaño de los Nodes[] sea mayor que 0 y realizar las siguientes tareas:
    • Inicialice la variable cnt como 0.
    • Inicializar un vector component_nodes[]. 
    • Iterar en un ciclo while hasta que cnt no sea igual a x.first y realizar las siguientes tareas:
      • Empuje el valor lat en los Nodes vectoriales [] en el vector component_nodes [] y extraiga ese valor de los Nodes [] y aumente el valor de cnt en 1.
    • Itere sobre el rango [1, component_nodes.size()) usando la variable i y realice las siguientes tareas:
      • Empuje el par {component_nodes[i], component_nodes[i-1]} en los bordes del vector [] .
• Después de realizar los pasos anteriores, imprima los bordes del vector [] como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to construct the graph for
// the given array
int constructConnectedComponent(int A[], int N)
{
  
    // Variable to check if all the values
    // are 1, then no need to form any edge
    bool flag = false;
  
    // Iterate through the array and store
    // the indices in a
    // map of same size connected component
    map<int, vector<int> > mp;
    for (int i = 0; i < N; i++) {
        mp[A[i]].push_back(i);
        if (A[i] != 1)
            flag = true;
    }
  
    if (!flag) {
        cout << "Graph already connected.\n";
        return 0;
    }
  
    // Check if the total size of vector is a
    // multiple of size
    for (auto x : mp) {
        if ((x.second).size() % x.first != 0) {
            cout << -1;
            return 0;
        }
    }
  
    // Make a vector to store the edges
    vector<pair<int, int> > edges;
  
    // Start constructing edges with each multiple
    // from the corresponding vector
    for (auto x : mp) {
        vector<int> nodes = x.second;
        while (!nodes.empty()) {
            int cnt = 0;
            vector<int> component_nodes;
            while (cnt != x.first) {
                component_nodes.push_back(nodes.back());
                nodes.pop_back();
                cnt++;
            }
  
            // Make edges between selected node
            for (int i = 1; i < component_nodes.size();
                 i++) {
                edges.push_back(
                    make_pair(component_nodes[i],
                              component_nodes[i - 1]));
            }
        }
    }
  
    // Print the edges of the graph
    cout << "[";
    for (int i = 0; i < edges.size(); i++) {
        cout << "{" << edges[i].first << ", "
             << edges[i].second << "}";
        if (i != edges.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]";
  
    return 0;
}
  
// Driver Code
int main()
{
    int N = 5;
    int A[] = { 2, 1, 1, 2, 1 };
  
    constructConnectedComponent(A, N);
  
    return 0;
}

[{0, 3}]

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)