Get the unique lengths of connected components of an undirected graph.

Problem Statement:

You are given an undirected graph with connected components.

Then you need to provide output of the unique length of connected components.

Example

The count of edges from the connected components are {2, 3, 2}

The unique count is 2.

Solution

Solution is very simple.

You need to do a DFS traversal to keep the track of connected components.

Then we use set STL to store the unique count.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_set> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
   void helper(int v, bool visited[], int& count); // helper function for count_max_sum_in_connected_components
public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   void count_unique_count_in_connected_components(vector<int> node_values); // returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
   adj[w].push_back(v); 
}


void Graph::helper(int v, bool visited[], int& count)
{
      visited[v] = true;

      count ++;

      for(auto i = adj[v].begin(); i != adj[v].end(); i++)
      {
         int adjVertex = *i;

         if ( !visited[adjVertex]){
             helper(adjVertex, visited, count);
         }
      }
}

void Graph::count_unique_count_in_connected_components(vector<int> node_values)
{
   bool *visited = new bool[V];
   for(int i = 0; i < V; i++)
   {
      visited[i] = false;
   }

   unordered_set<int> result;

    for (int v = 0; v < V; v++) 
    {
        if (visited[v] == false) {
            int count = 0;
            helper(v, visited, count);

            result.insert(count);
        }
    }

   cout << "The unique count of connected components are "<<result.size()<<endl;

}


int main()
{
   vector<int> node_values;
   node_values.push_back(15);
   node_values.push_back(25);
   node_values.push_back(35);
   node_values.push_back(45);
   node_values.push_back(55);
   node_values.push_back(65);

   Graph g(6);
   g.add_edge(1, 0);
   g.add_edge(2, 3);
   g.add_edge(3, 4);
   g.add_edge(4, 5);

   g.count_unique_count_in_connected_components(node_values);
   return 0;
}

Output:

The unique count of connected components are 2