Introduction 🤓
The problem to minimize the number of weakly connected nodes is a graph problem. It is usually referred to as a difficult graph problem. This article will discuss the weakly connected component algorithm to solve the problem.
Problem Statement 🤔
In the Ninja academy. Your sensei entrust a problem to minimize the number of weakly connected nodes to all his disciple. Here, you are provided with an undirected graph. Your task is to find the number of weakly connected nodes. After converting the graph into a directed graph.
You will report the number of weakly connected nodes in the directed graph.
Let’s see some sample examples for this problem.
Sample Examples 🧐
💡 Example 1:
⭐ Output: Two nodes with indegree zero.
Explanation: We can see that the indegree of nodes 1 and 3 are zero. Because these two nodes are pointing outwards. And no node is pointing towards them.
💡 Example 2:
⭐Output: No nodes with indegree zero.
Explanation: The indegree of the nodes in the above graph is either 1 or 2.
Weakly Connected Component Algorithm Approach
The algorithm finds sets of connected nodes in an undirected graph. Here all nodes in the same set form a connected component. It is often used early in analysis to know more about the structure of a graph. Using WCC to know about the graph structure enables running other algorithms independently. As a preprocessing step for directed graphs, it helps quickly in identifying the disconnected groups.
Algorithm ✨

We will first create a function to traverse the graph using DFS Algorithm.

Now we will create a function which computes the minimum number of disconnected components when a bidirected graph is converted to an undirected graph. To do so
 Declare and initialize an array
 We check if each node is visited at least once or not

We only start DFS from a node if and only if it is unvisited.
 After making the graph directed, we will iterate over the node set to count the number of nodes visited. And then storing it in the variable count.
 If count / 2 is equal to the number of nodes  1, then the number of weakly connected nodes is 1.
 Do the above process until all nodes are covered.
Implementation
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
// Set of nodes which are traversed
set<int> node;
vector<int> Graph[10001];
// building an undirected graph
void buildingGraph(int p[], int q[], int length)
{
for (int i = 0; i < length; i++)
{
int m = p[i];
int n = q[i];
Graph[m].push_back(n);
Graph[n].push_back(m);
}
}
// Function for traversing the graph using DFS approach and updating the set of nodes
void dfsearch(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]])
dfsearch(visit, Graph[src][i]);
}
// Function to compute the minimum number of disconnected components
int compute(int n)
{
// Declaring and initializing array
bool visit[n + 5];
memset(visit, false, sizeof(visit));
int numofnodes = 0;
// We check if node is visited or not
for (int i = 0; i < n; i++)
{
// Launching DFS
if (!visit[i])
{
// Clearing the set of nodes on every restart of DFS
node.clear();
// restarting DFS from an unvisited node.
dfsearch(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)
numofnodes++;
}
}
return numofnodes;
}
//Main Function//
int main()
{
FAST;
int u = 6,v = 4;
int p[u + 5] = {1, 1, 4, 4};
int q[u +5] = {2, 3, 5, 6};
// Now building graph in the form of an adjacency list
buildingGraph(p, q, v);
cout <<"There are "<< compute(v) << " weakly connected nodes";
return 0;
}
Output:
Time Complexity ⏳
The time complexity of the aboveused approach is O(V+E). Here, V is the vertices and E is the edges of the graph. We are using DFS, so our time complexity is O(V+E).
Space Complexity 🌌
The space complexity of the above approach is O(l). Here, l is the maximum length of the edge. As we are doing DFS in a linear fashion. This is why space complexity is O(l).