1.
Introduction
2.
Problem Statement
2.1.
Sample Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Approach
4.
Algorithm
5.
Code
5.1.
C++ Code
5.2.
Java Code
5.3.
Python Code
6.
Complexities
6.1.
Time Complexity
6.2.
Space Complexity
7.
7.1.
Which is faster, DFS or BFS?
7.2.
Which traversal is used to find the shortest path between two vertices?
7.3.
What is the maximum number of edges that an undirected graph can have?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Number of non-reachable nodes

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

## Introduction

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++){
if (visited[v]==false)
// recur for that node
}

}

// 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

// 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
{
}

// Driver code
int main()
{
int V = 8;

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
if(visited[v] == false) {
// recur for that node
}
}
}
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

// 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 main(String args[]) {

ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();

for (int i = 0; i < 8; i++) {
}

}
}``````

### Python Code

``````# to create an edge from u to v

# dfs search
# mark the current node as visited
visited[u]=1
# visit all the neighbours
# for every unvisited node call dfs

# function to calculate the no of non-reachable nodes
# 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

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

print("The number of non-reachable nodes are: " , end=" ")

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

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

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don't worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search.

Check out this problem - Connect Nodes At Same Level

If you wish to enhance your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, 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.

Do upvote if you find the blogs helpful.

Happy Learning!

Live masterclass