# Count single node isolated sub-graphs in a disconnected graph

A disconnected Graph with N vertices and K edges is given. The task is to find the count of singleton sub-graphs. A singleton graph is one with only single vertex.

Examples:

```Input :
Vertices : 6
Edges :    1 2
1 3
5 6
Output : 1
Explanation :  The Graph has 3 components : {1-2-3}, {5-6}, {4}
Out of these, the only component forming singleton graph is {4}.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is simple for graph given as adjacency list representation. We traverse the list and find the indices(representing a node) with no elements in list, i.e. no connected components.

Below is the representation :

## C++

 `// CPP code to count the singleton sub-graphs ` `// in a disconnected graph ` `#include ` `using` `namespace` `std; ` ` `  `// Function to compute the count ` `int` `compute(vector<``int``> graph[], ``int` `N) ` `{ ` `    ``// Storing intermediate result ` `    ``int` `count = 0; ` ` `  `    ``// Traversing the Nodes ` `    ``for` `(``int` `i = 1; i <= N; i++) ` ` `  `        ``// Singleton component ` `        ``if` `(graph[i].size() == 0) ` `            ``count++;     ` ` `  `    ``// Returning the result ` `    ``return` `count; ` `} ` ` `  `// Driver ` `int` `main() ` `{ ` `    ``// Number of nodes ` `    ``int` `N = 6; ` ` `  `    ``// Adjacency list for edges 1..6 ` `    ``vector<``int``> graph; ` ` `  `    ``// Representing edges ` `    ``graph.push_back(2); ` `    ``graph.push_back(1); ` ` `  `    ``graph.push_back(3); ` `    ``graph.push_back(2); ` ` `  `    ``graph.push_back(6); ` `    ``graph.push_back(5); ` ` `  `    ``cout << compute(graph, N); ` `} `

## Python3

# Python code to count the singleton sub-graphs
# in a disconnected graph

# Function to compute the count
def compute(graph, N):
# Storing intermediate result
count = 0

# Traversing the Nodes
for i in range(1, N+1):

# Singleton component
if (len(graph[i]) == 0):
count += 1

# Returning the result
return count

# Driver
if __name__ == ‘__main__’:

# Number of nodes
N = 6

# Adjacency list for edges 1..6
graph = [[] for i in range(7)]

# Representing edges
graph.append(2)
graph.append(1)

graph.append(3)
graph.append(2)

graph.append(6)
graph.append(5)

print(compute(graph, N))

Output:

```1
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Graph graph-connectivity Graph

code

load comments