In this article, we will discuss the Number of Connected Components in an Undirected Graph problem, along with a sample test case and approach to solve the problem.

Problem Statement

Given an undirected graph having V nodes and a set of vertices, the task is to find the number of nodes that are non-reachable from the given node using the depth-first search.

Sample Example

Input

5
0 1
0 2
1 2
3 4

Output

2

Explanation

For the above graph, if the node with the value '0' is considered the head, then the nodes with values 1, 2, and 0 will only be reachable. Since nodes with values 3 and 4 are non-reachable, therefore the count of nodes that are non-reachable from the node with value 0 is 2.

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

Approach

We are given an undirected graph having V nodes, and we are supposed to find the number of non-reachable nodes from the given head node.

We can find the number of non-reachable nodes from the given head node using either of the graph traversal algorithms that are BFS & DFS Algorithm. As mentioned above in the problem statement, we will use the DFS approach. As the graph given in the input is an undirected graph, therefore, all of the vertices that are part of the disconnected component are non-reachable nodes.

We maintain a visited array to keep track of all the unvisited nodes and a count variable to find the number of non-reachable nodes. We call a depth-first search from the given head node. This call will mark all of the nodes which are connected to the head node as visited. Now we can simply traverse over the visited array, and for every unvisited node, we just increment the count variable and return it at the end.

Algorithm

Keep track of a count variable and initialize it with 0. Also, maintain a visited array, initially marking every node as unvisited.

Make a DFS call from the given head node.

For every node visited, mark it as true in the visited array.

Now traverse through the visited array, and increment the count variable for every unvisited node.

Return the count variable.

Code

The implementation of the above algorithm in various programming languages is mentioned below:

C++ Code

#include <bits/stdc++.h>
using namespace std;
void DFS(int u, vector<bool> &visited, vector<int> adj[])
{
// mark the current node as visited
visited[u] = true;
// visit the neighbours
for(int i = 0; i<adj[u].size(); i++){
int v = adj[u][i];
if (visited[v]==false)
// recur for that node
DFS(v, visited, adj);
}
}
// function to calculate the no of non-reachable nodes
int getCount(vector<int> adj[], int V, int start)
{
// stores the no of non-reachable nodes
int count=0;
// visited array stores whether or not a node has been visited
vector<bool> visited(V, false);
// DFS call to mark all the nodes connected to start as visited
DFS(start, visited, adj);
// for every node
for (int u = 0; u < V; u++) {
// if not visited, increment count
if (visited[u] == false) {
count+=1;
}
}
return count;
}
// function to add an undirected edge between u & v
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Driver code
int main()
{
int V = 8;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 3);
addEdge(adj, 1, 2);
addEdge(adj, 4, 5);
addEdge(adj, 5, 7);
addEdge(adj, 4, 6);
cout<<"The number of non-reachable nodes from node "<< 2 <<" are: "<<getCount(adj, V, 2);
return 0;
}

Java Code

import java.util.*;
class Solution
{
public static void DFS(int u, boolean visited[], ArrayList<ArrayList<Integer>> adj) {
//mark the current node as visited
visited[u] = true;
// visit the neighbours
for(Integer v: adj.get(u)) {
if(visited[v] == false) {
// recur for that node
DFS(v, visited, adj);
}
}
}
public static void getCount(int V, ArrayList<ArrayList<Integer>> adj, int start)
{
// stores the no of non-reachable nodes
int count=0;
//visited array stores whether or not anode has been visited
boolean visited[] = new boolean[V];
// DFS call to mark all the nodes connected to start as visied
DFS(start, visited, adj);
// for every node
for(int i = 0;i<V;i++) {
// if not visited
if(visited[i]==false) {
// increment count
count+=1;
}
}
System.out.print("The number of non-reachable nodes from " + start +" are " + count);
}
// function to add an undirected edge between u & v
public static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v){
adj.get(u).add(v);
adj.get(v).add(u);
}
public static void main(String args[]) {
ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();
for (int i = 0; i < 8; i++) {
adj.add(new ArrayList < > ());
}
addEdge(adj, 0, 1);
addEdge(adj, 0, 3);
addEdge(adj, 1, 2);
addEdge(adj, 4, 5);
addEdge(adj, 5, 7);
addEdge(adj, 4, 6);
getCount(8, adj, 2);
}
}

Python Code

# to create an edge from u to v
def addEdge(adj, u, v):
adj[u].append(v)
adj[v].append(u)
# dfs search
def DFS(adj, visited, u):
# mark the current node as visited
visited[u]=1
# visit all the neighbours
for i in range(len(adj[u])):
# for every unvisited node call dfs
if visited[adj[u][i]] == 0:
DFS(adj, visited, adj[u][i])
# function to calculate the no of non-reachable nodes
def getCount(adj, V, start):
# stores the no of non-reachable nodes
count = 0
# visited is used to check whether or not a node is visited
visited = [0 for i in range(V)]
# DFS call to mark all the nodes connected to start as visited
DFS(adj, visited, start)
for u in range(V):
# for every unvisited node
if visited[u]==0:
# increment the no of non-reachable nodes
count+=1;
print(count)
# Driver Code
if __name__ == '__main__':
V = 8
adj = [[] for i in range(V)]
addEdge(adj, 0, 1);
addEdge(adj, 0, 3);
addEdge(adj, 1, 2);
addEdge(adj, 4, 5);
addEdge(adj, 5, 7);
addEdge(adj, 4, 6);
print("The number of non-reachable nodes are: " , end=" ")
getCount(adj, V, 2)

Output:

The number of non-reachable nodes are: 4

Complexities

Time Complexity

O(V+E), where V denotes the number of vertices and E denotes the number of edges

Space Complexity

O(V), where V denotes the number of vertices

Frequently Asked Questions

Which is faster, DFS or BFS?

Even though the time complexity of both is the same, depending on the problem, the execution time can vary. For example, If the search can be aborted once the element is found and the element is present at a higher level in the tree, then BFS is faster in that case. But if the element is very deep in the tree, then DFS will be faster.

Which traversal is used to find the shortest path between two vertices?

The BFS traversal is used to find the shortest path between two vertices.

What is the maximum number of edges that an undirected graph can have?

The maximum number of edges that an undirected graph can have is n(n-1)/2, where n is the number of nodes.

Conclusion

In this article, we have extensively discussed the Number of non-reachable nodes problem.

If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company.