Minimize the Number of Weakly Connected Nodes

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 in-degree 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 in-degree zero.

Explanation: The in-degree 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 ✨

1. We will first create a function to traverse the graph using DFS Algorithm.
    
2. Now we will create a function which computes the minimum number of disconnected components when a bi-directed 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.
      
3. 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. 
4. If count / 2 is equal to the number of nodes - 1, then the number of weakly connected nodes is 1.
5. 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;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity ⏳

The time complexity of the above-used 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).