Approach
First, think of a case where the size of the components of all the nodes are 1.
What does this imply about the graph? It implies there are no edges in the graph, and we do not need to do anything. The output will be an empty list.
Now, the nodes for which A[i]=1 will not form edges as the size of its component is 1. So, we can safely ignore such nodes.
Next comes the real problem. The nodes i, for which A[i] is not equal to 1.
If for node i, the size of its component is A[i]=k, this means that there should be k1 more nodes having their size of components equal to k.
Now, suppose, for m nodes, the size of their components is k. Then, m must be divisible by k. Why? Because we should be able to group the m nodes into components, each is size k.
Example  if m=4 and k=2 then the vertices v0, v1 form one component and {v2,v3} form other component.
Next, if m=5 and k=2, then we cant divide the 5 vertices into components of size 2 as one component will have only one vertex, so its size will be 2. and hence it's not valid.
We have to do 2 things:
 First, we will check if it is possible to construct a valid graph from the given array A[] by the above condition.

Then we will proceed to form the edges of a possible graph.
The steps of the implementation of the approach are as follows:

First, check if the size of components of all the nodes are 1 or not. If all are 1, that means the graph has no edges and we will return an empty list.

To store the count ‘m’ of all the nodes having the same size of components, we will use a map where the key k is the size of the component and its value is a vector of all nodes i having componentsSize[i]=k.

Check if a valid graph is possible or not. Iterate over all the elements of the map, and for each element k, get the size m of the vector corresponding to it. If m%k==0, for all elements then a valid graph is possible; else, return 1.

Initialize a vector of pairs to store the edges of the graph to be constructed.

Iterate over every element of the map. If there are m nodes in the vector corresponding to component size, we will divide the m nodes into groups of size = component_size to form the graph.

Compute the number of groups of nodes possible by numGroups = Number of nodes/Component_size.

For each group, form the edges between the adjacent nodes and push the pair in the vector of edges.
 Finally, print the edges.
In the next section, let’s see the code implementation and the time and space complexity analysis.
C++ Implementation
/*C++ code to construct a Graph from the size of components of each node*/
#include <bits/stdc++.h>
using namespace std;
void graphFromComponentSize(vector<int> &componentsSize, int n)
{
bool flag = false;
unordered_map<int, vector<int>> mp;
for (int i = 0; i < n; i++)//O(n)
{
mp[componentsSize[i]].push_back(i);
if (componentsSize[i] != 1)
flag = true;
}
if (!flag)
{
cout << "No edges exist in the possible graph\n";
return;
}
for (auto a : mp)//O(n)
{
int component_size, num_nodes;
component_size = a.first;
num_nodes = a.second.size();
if (num_nodes % component_size != 0)
{
cout << "No valid graph is possible\n";
return;
}
}
vector<pair<int, int>> edges;
for (auto a : mp)
{
vector<int> nodes = a.second;
int component_size = a.first;
// divide the nodes into groups of size= component_size
int numGroups = nodes.size() / component_size;
for (int i = 0; i < numGroups; i++)
{
int start = i * component_size;
for (int j = start + 1; j < start + component_size; j++)
{
edges.push_back({nodes[j], nodes[j  1]});
}
}
}
cout << "[";
for (int i = 0; i < edges.size(); i++)
{
cout << "{" << edges[i].first << ", "
<< edges[i].second << "}";
if (i != edges.size()  1)
{
cout << ", ";
}
}
cout << "]";
}
int main()
{
int n = 6;
vector<int> componentsSize = {3, 2, 2, 3, 3, 1};
graphFromComponentSize(componentsSize, n);
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
Output
[{2, 1}, {3, 0}, {4, 3}]
Time Complexity
O(n), where n=number of nodes in the graph.
In the function, graphFromComponentSize(), we first iterate over all the nodes to store the values in a map which is an O(n) operation.
Next, we check if a valid graph is possible or not by iterating over all elements of the map, which is also an O(n) operation.
Then, we again iterate through all the map elements to form the edges, and since we iterate through every node only once, its complexity is also O(n).
Hence, the total time complexity is O(n).
Space Complexity
O(n), where n=number of nodes in the graph. Since we use a map to store the size of a component as a key and vector of nodes corresponding to it.
Frequently Asked Questions

What are graph data structures used for?
Graphs in data structures are used to represent the relationships between objects.

What is a connected component in graph theory?
A connected component or simply component of an undirected graph is a subgraph in which each pair of nodes is connected with each other via a path.

Which graph traversal can be used to determine the connected components in a graph?
We can use a traversal algorithm, either depthfirst or breadthfirst, to find the connected components of an undirected graph.
Key Takeaways
In this article, we discussed an interesting problem based on graphs that are crucial for tech interviews. We solved the problem using a standard concept in graph theory called connected components in an undirected graph.
Before ending this article, some of the followup problems that you can solve based on a similar concept are:
If you want to get confident about the various algorithms in graphs, check out Greedy Algorithms in Graph to learn all the important algorithms like Kruskal’s algorithm, Prim’s algorithm etc., on graphs in one place.
Also, practice TOP GRAPHS INTERVIEW QUESTIONS from Coding Ninjas Studio to ace your next technical interview.
Are you planning to ace the interviews of reputed productbased companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!