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