# 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