C++ program to Minimize the number of weakly connected nodes

In this tutorial, we will go through the C++ program to Minimize the number of weakly connected nodes. In the end, we will implement the code for it.

It is defined as nodes which are having 0 indegrees are called a weakly connected graph.

Suppose we are having an undirected graph.  Our task is to find the minimum number of weakly connected nodes.  To do this we should convert the graph into undirected.

Let us look over an example

 

Input : 4 4 
        0 1
        1 2
        2 3
        3 0
Output : 0 disconnected components 
Do the above steps to traverse the graph.

Input : 6 5
       1 2
       2 3
       4 5
       4 6
       5 6
Output : 1 disconnected components

Now we will go through the best approach for it. One should find a node that helps in traversing maximum nodes in a single walk. To cover all possible paths,  graph traversal is used first to traverse the graph.  Now,  iterate through the graph again and check which nodes are having 0 indegrees.

#include <bits/stdc++.h> namespace std;
set<int> node; 
vector<int> Graph[10001]; 

 
void dfs(bool visit[], int src) 
{ 
  visit[src] = true; 
  node.insert(src); 
  int len = Graph[src].size(); 
  for (int i = 0; i < len; i++)	 
    if (!visit[Graph[src][i]])		 
      dfs(visit, Graph[src][i]); 
} 

void buildGraph(int x[], int y[], int len){ 

  for (int i = 0; i < len; i++) 
  { 
    int p = x[i]; 
    int q = y[i]; 
    Graph[p].push_back(q); 
    Graph[q].push_back(p); 
  } 
} 


int compute(int n) 
{ 
  
  bool visit[n + 5]; 
  memset(visit, false, sizeof(visit)); 
  int number_of_nodes = 0; 

  
  for (int i = 0; i < n; i++) 
  {  
    if (!visit[i]) { 
 
      node.clear(); 
      
      
      dfs(visit, i); 
      
      int count = 0;		 
      for (auto it = node.begin(); it != node.end(); ++it) 
        count += Graph[(*it)].size(); 
    
      count /= 2;		 
      if (count == node.size() - 1) 
      number_of_nodes++; 
    } 
  } 
  return number_of_nodes; 
} 

//Driver function 
int main() 
{ 
  int n = 6,m = 4; 
  int x[m + 5] = {1, 1, 4, 4}; 
  int y[m+5] = {2, 3, 5, 6}; 


  // Building graph in the form of a adjacency list 
  buildGraph(x, y, n); 
  cout << compute(n) << " weakly connected nodes"; 
  
  return 0; 
} 
OUTPUT;

2 weakly connected nodes

Also, read: Program to Rotate Doubly linked list by N nodes in C++


Leave a Reply

Your email address will not be published. Required fields are marked *