Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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.

Number of Connected Components in an Undirected Graph

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

Sample Input graph

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.

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!

Thank you
Previous article
Count the number of magical Indices in an array
Next article
Number of Connected Components in an Undirected Graph
Live masterclass