Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 🤓
1.1.
Problem Statement 🤔
1.2.
Sample Examples 🧐
2.
Weakly Connected Component Algorithm Approach
2.1.
Algorithm ✨
2.2.
Implementation 
2.2.1.
Time Complexity ⏳
2.2.2.
Space Complexity 🌌
3.
Frequently Asked Questions 
3.1.
What do weakly connected nodes of a graph mean?
3.2.
Can a graph be both strongly and weakly connected at the same time?
3.3.
What does it mean to have a weakly connected component in the graph?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Minimize the Number of Weakly Connected Nodes

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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. 

Minimize the number of weakly connected nodes

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. 

problem statement

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: 

example


⭐ 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:

example

⭐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;
}

Output:

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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions 

What do weakly connected nodes of a graph mean?

A graph is weakly connected if there isn't any path between any two pairs of vertices. Hence, if graph G doesn't contain a directed path then it is weakly connected.

Can a graph be both strongly and weakly connected at the same time?

Yes, a graph can, according to the definitions, a graph can definitely be both weakly and strongly connected at the same time.

What does it mean to have a weakly connected component in the graph?

A weakly connected component (WCC) is a subgraph of an original graph. Here all the vertices are connected to each other by some path, ignoring the direction of the edges.

Conclusion

This article briefly discussed the problem to minimize the number of weakly connected nodes.

We hope that this blog had help you enhance your knowledge about the problem to minimize the number of weakly connected nodes and if you would like to learn more, check out our articles Check Identical TreesBoundary Traversal of Binary TreeLevel Order Traversal of a Binary TreeConvert BST to the Greatest Sum TreeReplace each node in a binary tree with a sum of its in order predecessor and successor, and Print Nodes between two given Level Numbers of a Binary Tree. You can also refer to our guided path on the basics of java and many more on our Website.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series. You can also participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy learning!

Previous article
Multistage Graph
Next article
Minimum Edges Required to Make Euler Circuit
Live masterclass