Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ Code
3.2.
Python Code
3.3.
Java Code
4.
Frequently Asked Questions
4.1.
What is the benefit of using an array list over an array in Java?
4.2.
Why is the time complexity of the above approach O(n+m) and not O(n)?
4.3.
Can this problem be solved with a time complexity less than O(n + m )?
5.
Conclusion 
Last Updated: Mar 27, 2024
Medium

Count single node isolated sub-graphs in a disconnected graph

Author Pradeep Kumar
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this article, we will look at the problem of counting single node isolated sub-graphs in a disconnected graph. Single node isolated sub-graphs are the subgraphs in a graph which has only one vertex and are not connected to any other vertex of the graph. 

For the implementation, Vectors of C++ are used; if you are not familiar with vectors, you can check out this article.

Count single node isolated sub-graphs in a disconnected graph

Problem Statement

Given a disconnected graph with N vertices and M edges, find out the total number of single node isolated sub-graphs.

Examples:

Input: 
Vertices(N) : 7
Edges(M):    2
        2 3
        5 6       
Output: 3
Explanation: This Graph as 5 connected components which are: {2,3} , {5,6}, {1}, {4}, {7}. Out of these 5 components, 3 of them are single node isolated sub-graphs. Those 3 are {1}, {4}, {7}.

Input Graph    

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

Solution Approach

In this approach, we simply traverse over the adjacency list and check for the elements which have no vertex in their list. The algorithm is as follows:

Step 1: Traverse over the adjacency list

Step 2: For every index, count the number of elements in its respective list.

Step 3: If the count of elements is zero. Increase the count of single node isolated sub-graphs by one.

Step 4: Go to the next index and check for the condition mentioned in step 3.

Step 5: Once the traversing over the graph is complete, print the count of single node isolated sub-graphs.  

Step 6: If there are no single node isolated sub-graphs, print 0.

C++ Code

// Cpp program to calculate the count of single node isolated sub graphs

#include<iostream>
#include<vector>

using namespace std;

int countSingleNodeIsolatedSubGraphs(int n, vector<vector<int>> & adj_list){
    int count=0;
    int index=1;
    while(index<=n){
        if(adj_list[index++].size()==0){
            count++;
        }
    }
    return count;
}

int main(){
    // Input
    int n = 7; // total vertices
    int m = 2; // total edges
    vector<pair<int,int>> edges = {{2,3}, {5,6}}; // 2 edges

    vector<vector<int>> adj_list(n+1, vector<int>{}); // adjacency list of elements from 1 to 7.

    for(auto it: edges){
        adj_list[it.first].push_back(it.second);
        adj_list[it.second].push_back(it.first);
    }

    int count = countSingleNodeIsolatedSubGraphs(n, adj_list); // calling func to calculate the total number of single node isolated sub-graphs

    cout<<"Total Single Node isolated Sub Graphs: "<< count<<endl;

    return 0;
}

Python Code

# Python program to calculate the count of single node isolated sub graphs

def countSingleNodeIsolatedSubGraphs(n, adj_list):
    count=0
    index=1
    while(index<=n):
        if(len(adj_list[index])==0):
            count+=1
        index+=1
    return count

if __name__=="__main__":
    # Input
    n = 7 # total vertices
    m = 2 # total edges
    edges = [[2,3], [5,6]] # 2 edges

    adj_list = []
    for i in range(n+1): # adjacency list of elements from 1 to 7.
        adj_list.append([])

    for i in range(len(edges)):
        adj_list[edges[i][0]].append(edges[i][1])
        adj_list[edges[i][1]].append(edges[i][0])

    count = countSingleNodeIsolatedSubGraphs(n, adj_list) # calling func to calculate the total number of single node isolated sub-graphs

    print("Total Single Node isolated Sub Graphs: ", count)

Java Code

//  Java program to calculate the count of single node isolated sub graphs
import java.util.*;
public class test{

  public static int countSingleNodeIsolatedSubGraphs(int n, ArrayList<ArrayList<Integer>> adj_list){
    int count=0;
    int index=1;
    while(index<=n){
        if((adj_list.get(index++)).size()==0){
            count++;
        }
    }
    return count;
}
 
  public static void main(String[] args) {
    // Input
    int n = 7; // total vertices
    int m = 2; // total edges
    int[][] edges = {{2,3}, {5,6}}; // 2 edges

    ArrayList<ArrayList<Integer>>adj_list = new ArrayList<ArrayList<Integer>>(n+1); // adjacency list of elements from 1 to 7.

    for(int i=0;i<=n;i++){
      adj_list.add(new ArrayList<Integer>());
    }

    for(int i=0;i<m;i++){
        adj_list.get(edges[i][0]).add(edges[i][1]);
        adj_list.get(edges[i][1]).add(edges[i][0]);
    }

    int count = countSingleNodeIsolatedSubGraphs(n, adj_list); // calling func to calculate the total number of single node isolated sub-graphs
    System.out.println("Total Single Node isolated Sub Graphs: " + count);
  }
}

 

Output:

Total Single Node isolated Sub Graphs: 3

Time Complexity:  O(n+m), where n is the number of vertices and m is the number of edges.

Space Complexity: O(n+m), where n is the number of vertices and m is the number of edges.

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

What is the benefit of using an array list over an array in Java?

An array has a fixed size, and an array list has a dynamic size. You can add any number of elements to an array list, and it will increase and decrease its size accordingly. In case when you are not sure about the number of elements you might add to an array, it is better to use an array list instead.

Why is the time complexity of the above approach O(n+m) and not O(n)?

There are two components in this problem which add up to the time complexity, which are the time required to count the number of single node isolated subgraphs and the time required to create the adjacency list. The first can be done in O(n), but for the second one, you need O(n+m) as you need to store all the edges in the adjacency list.

Can this problem be solved with a time complexity less than O(n + m )?

To count the total number of single node isolated sub-graphs, you need to iterate over all the nodes and edges in the graph. That can't be done in a time complexity less than O(n+m).

Conclusion 

In this article, we have extensively discussed the problem of counting single node isolated sub-graphs in a disconnected graph. We hope that this blog has helped you enhance your knowledge. To learn more, check out our article on Number of connected components in an undirected graph

Check out this problem - Connect Nodes At Same Level

And also, check out the awesome content on the Coding Ninjas Website, Android DevelopmentCoding Ninjas Studio ProblemsCoding Ninjas Studio Interview BundleCoding Ninjas Studio Interview ExperiencesCoding Ninjas CoursesCoding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blog to help other ninjas grow. Happy Coding!

Thank you

Previous article
Transpose Graph
Next article
Dinic’s algorithm for Maximum Flow
Live masterclass