Construct a Graph from size of components for each node
Given an array A[] of size N, for each index i in the range [0, N) the value A[i] denotes the size of the connected component of node i. The task is to find the edges for the possible graph else print -1.
Note: There may be more than 1 possible answers for each array. Print any one of them.
Examples:
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.
Approach: The idea is to observe that all the same component sizes can be connected with each other using total nodes equal to the size of the array value. So, store all the nodes with the same index value into a map. The values of nodes can be stored with a map structure map<int, vector<int>>. Check for each size of connected component that the corresponding total nodes are a multiple of the size. If for any connected component the above condition fails then there will be no valid graph. Return -1 immediately. Otherwise for all multiple stores the vertices and connect them adjacently. Store all edges in an array and output the result. Follow the steps below to solve the problem:
- Initialize a boolean variable flag as false to check if all the values are 1. If so, then there is no need to form any edge.
- Initialize a map of vector mp[] to store the indices for a particular connected component size.
- Iterate over the range [0, N) using the variable i and perform the following tasks:
- Push the value i into the vector in the map at A[i].
- If A[i] is not equal to 1, then set the value of flag as true.
- If flag is false, then return.
- Iterate over the map using the variable x and perform the following tasks:
- If x.second.size() is not divisible by x.first, then print -1 and return 0.
- Initialize a vector of pair of int edges[] to store the edges.
- Iterate over the map using the variable x and perform the following tasks:
- Initialize a vector nodes[] as the vector at the current position.
- Iterate in a while loop till the size of nodes[] is greater than 0 and perform the following tasks:
- Initialize the variable cnt as 0.
- Initialize a vector component_nodes[].
- Iterate in a while loop till cnt is not equal to x.first and perform the following tasks:
- Push the last value in the vector nodes[] into the vector component_nodes[] and pop that value from nodes[] and increase the value of cnt by 1.
- Iterate over the range [1, component_nodes.size()) using the variable i and perform the following tasks:
- Push the pair {component_nodes[i], component_nodes[i-1]} into the vector edges[].
- After performing the above steps, print the vector edges[] as the answer.
Below is the implementation of the above approach:
C++
// 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; } |
Java
import java.util.*; public class GFG { static void constructConnectedComponent( int [] A, int N) { // Variable to check if all the values // are 1, then no need to form any edge boolean flag = false ; // Create a dictionary to store the indices of the // same size connected component Map<Integer, List<Integer> > mp = new HashMap<Integer, List<Integer> >(); for ( int i = 0 ; i < N; i++) { if (!mp.containsKey(A[i])) { mp.put(A[i], new ArrayList<Integer>()); } mp.get(A[i]).add(i); if (A[i] != 1 ) { flag = true ; } } if (!flag) { System.out.println( "Graph already connected." ); return ; } // Check if the total size of the list is a multiple // of its key for (Map.Entry<Integer, List<Integer> > entry : mp.entrySet()) { if (entry.getValue().size() % entry.getKey() != 0 ) { System.out.println(- 1 ); return ; } } // Make a List to store the edges List<Tuple<Integer, Integer> > edges = new ArrayList<Tuple<Integer, Integer> >(); // Start constructing edges with each multiple from // the corresponding list for (Map.Entry<Integer, List<Integer> > entry : mp.entrySet()) { List<Integer> nodes = entry.getValue(); while (nodes.size() > 0 ) { int cnt = 0 ; List<Integer> componentNodes = new ArrayList<Integer>(); while (cnt != entry.getKey()) { componentNodes.add( nodes.get(nodes.size() - 1 )); nodes.remove(nodes.size() - 1 ); cnt++; } // Make edges between selected nodes for ( int i = 1 ; i < componentNodes.size(); i++) { edges.add( new Tuple<Integer, Integer>( componentNodes.get(i), componentNodes.get(i - 1 ))); } } } // Print the edges of the graph System.out.print( "[" ); for ( int i = 0 ; i < edges.size(); i++) { System.out.printf( "(%d, %d)" , edges.get(i).getItem1(), edges.get(i).getItem2()); if (i != edges.size() - 1 ) { System.out.print( ", " ); } } System.out.println( "]" ); } public static void main(String[] args) { int N = 5 ; int [] A = { 2 , 1 , 1 , 2 , 1 }; constructConnectedComponent(A, N); } } // Class for creating a tuple in Java class Tuple<X, Y> { public final X x; public final Y y; public Tuple(X x, Y y) { this .x = x; this .y = y; } public X getItem1() { return x; } public Y getItem2() { return y; } } |
Python
# Python program for the above approach # Function to construct the graph for # the given array def constructConnectedComponent(A, N): # Variable to check if all the values # are 1, then no need to form any edge flag = False # Iterate through the array and store # the indices in a # map of same size connected component mp = {} for i in range (N): if A[i] not in mp: mp[A[i]] = [] mp[A[i]].append(i) if A[i] ! = 1 : flag = True if not flag: print ( "Graph already connected." ) return # Check if the total size of vector is a # multiple of size for x in mp: if len (mp[x]) % x ! = 0 : print ( - 1 ) return # Make a vector to store the edges edges = [] # Start constructing edges with each multiple # from the corresponding vector for x in mp: nodes = mp[x] while nodes: cnt = 0 component_nodes = [] while cnt ! = x: component_nodes.append(nodes.pop()) cnt + = 1 # Make edges between selected node for i in range ( 1 , len (component_nodes)): edges.append((component_nodes[i], component_nodes[i - 1 ])) # Print the edges of the graph print ( "[" ) for i in range ( len (edges)): print ( "{" + str (edges[i][ 0 ]) + ", " + str (edges[i][ 1 ]) + "}" ) if i ! = len (edges) - 1 : print ( ", " ) print ( "]" ) # Driver Code if __name__ = = "__main__" : N = 5 A = [ 2 , 1 , 1 , 2 , 1 ] constructConnectedComponent(A, N) |
C#
using System; using System.Collections.Generic; class GFG { static void ConstructConnectedComponent( int [] A, int N) { // Variable to check if all the values // are 1, then no need to form any edge bool flag = false ; // Create a dictionary to store the indices of the same size connected component Dictionary< int , List< int >> mp = new Dictionary< int , List< int >>(); for ( int i = 0; i < N; i++) { if (!mp.ContainsKey(A[i])) { mp[A[i]] = new List< int >(); } mp[A[i]].Add(i); if (A[i] != 1) flag = true ; } if (!flag) { Console.WriteLine( "Graph already connected." ); return ; } // Check if the total size of the list is a multiple of its key foreach ( var x in mp) { if ((x.Value).Count % x.Key != 0) { Console.WriteLine(-1); return ; } } // Make a List to store the edges List<Tuple< int , int >> edges = new List<Tuple< int , int >>(); // Start constructing edges with each multiple from the corresponding list foreach ( var x in mp) { List< int > nodes = x.Value; while (nodes.Count > 0) { int cnt = 0; List< int > componentNodes = new List< int >(); while (cnt != x.Key) { componentNodes.Add(nodes[nodes.Count - 1]); nodes.RemoveAt(nodes.Count - 1); cnt++; } // Make edges between selected nodes for ( int i = 1; i < componentNodes.Count; i++) { edges.Add(Tuple.Create(componentNodes[i], componentNodes[i - 1])); } } } // Print the edges of the graph Console.Write( "[" ); for ( int i = 0; i < edges.Count; i++) { Console.Write( "({0}, {1})" , edges[i].Item1, edges[i].Item2); if (i != edges.Count - 1) { Console.Write( ", " ); } } Console.WriteLine( "]" ); } static void Main( string [] args) { int N = 5; int [] A = { 2, 1, 1, 2, 1 }; ConstructConnectedComponent(A, N); } } // This code is contributed by lokeshpotta20. |
Javascript
// JavaScript program for the above approach // Function to construct the graph for // the given array function constructConnectedComponent(A, N) { // Variable to check if all the values // are 1, then no need to form any edge let flag = false ; // Iterate through the array and store // the indices in a map of same size connected component let mp = {}; for (let i = 0; i < N; i++) { if (!(A[i] in mp)) { mp[A[i]] = []; } mp[A[i]].push(i); if (A[i] != 1) { flag = true ; } } if (!flag) { console.log( "Graph already connected." ); return ; } // Check if the total size of vector is a // multiple of size for (let x in mp) { if (mp[x].length % x != 0) { console.log(-1); return ; } } // Make a vector to store the edges let edges = []; // Start constructing edges with each multiple // from the corresponding vector for (let x in mp) { let nodes = mp[x]; while (nodes.length) { let cnt = 0; let component_nodes = []; while (cnt != x) { component_nodes.push(nodes.pop()); cnt += 1; } // Make edges between selected node for (let i = 1; i < component_nodes.length; i++) { edges.push([component_nodes[i], component_nodes[i - 1]]); } } } // Print the edges of the graph process.stdout.write( "[" ); for (let i = 0; i < edges.length; i++) { process.stdout.write( "{" + edges[i][0] + ", " + edges[i][1] + "}" ); if (i != edges.length - 1) { process.stdout.write( ", " ); } } console.log( "]" ); } // Driver Code let N = 5; let A = [2, 1, 1, 2, 1]; constructConnectedComponent(A, N); |
[{0, 3}]
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)