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 Development, Coding Ninjas Studio Problems, Coding Ninjas Studio Interview Bundle, Coding Ninjas Studio Interview Experiences, Coding Ninjas Courses, Coding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blog to help other ninjas grow. Happy Coding!
234+ registered 
