Number of non-reachable nodes

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

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

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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

Do upvote if you find the blogs helpful.

Happy Learning!