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 6Output :1Explanation :The Graph has 3 components : {1-2-3}, {5-6}, {4} Out of these, the only component forming singleton graph is {4}.

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 <bits/stdc++.h> ` `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[7]; ` ` ` ` ` `// Representing edges ` ` ` `graph[1].push_back(2); ` ` ` `graph[2].push_back(1); ` ` ` ` ` `graph[2].push_back(3); ` ` ` `graph[3].push_back(2); ` ` ` ` ` `graph[5].push_back(6); ` ` ` `graph[6].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[1].append(2)

graph[2].append(1)

graph[2].append(3)

graph[3].append(2)

graph[5].append(6)

graph[6].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.

## leave a comment

## 0 Comments