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

• Difficulty Level : Basic
• Last Updated : 19 Jul, 2022

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}.```

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);``}`

## Java

 `// Java code to count the singleton sub-graphs``// in a disconnected graph``import` `java.util.*;` `class` `GFG``{` `// Function to compute the count``static` `int` `compute(``int` `[]graph, ``int` `N)``{``    ``// Storing intermediate result``    ``int` `count = ``0``;``    ` `    ``// Traversing the Nodes``    ``for` `(``int` `i = ``1``; i < ``7``; i++)``    ``{``        ``// Singleton component``        ``if` `(graph[i] == ``0``)``            ``count++;    ``    ``}``        ` `    ``// Returning the result``    ``return` `count;``}` `// Driver Code``public` `static` `void` `main(String[] args)``{``    ``// Number of nodes``    ``int` `N = ``6``;` `    ``// Adjacency list for edges 1..6``    ``int` `[]graph = ``new` `int``[``7``];``    ``// Representing edges``    ``graph[``1``] = ``2``;``    ``graph[``2``] = ``1``;``    ``graph[``2``] = ``3``;``    ``graph[``3``] = ``2``;``    ``graph[``5``] = ``6``;``    ``graph[``6``] = ``5``;` `    ``System.out.println(compute(graph, N));``}``}` `// This code is contributed by PrinciRaj1992`

## 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))`

## C#

 `// C# code to count the singleton sub-graphs``// in a disconnected graph``using` `System;` `class` `GFG``{` `// Function to compute the count``static` `int` `compute(``int` `[]graph, ``int` `N)``{``    ``// Storing intermediate result``    ``int` `count = 0;``    ` `    ``// Traversing the Nodes``    ``for` `(``int` `i = 1; i < 7; i++)``    ``{``        ``// Singleton component``        ``if` `(graph[i] == 0)``            ``count++;    ``    ``}``        ` `    ``// Returning the result``    ``return` `count;``}` `// Driver Code``public` `static` `void` `Main(String[] args)``{``    ``// Number of nodes``    ``int` `N = 6;` `    ``// Adjacency list for edges 1..6``    ``int` `[]graph = ``new` `int``;``    ` `    ``// Representing edges``    ``graph = 2;``    ``graph = 1;``    ``graph = 3;``    ``graph = 2;``    ``graph = 6;``    ``graph = 5;` `    ``Console.WriteLine(compute(graph, N));``}``}` `// This code is contributed by 29AjayKumar`

## Javascript

 ``

Output

`1`

This article is contributed by Rohit Thapliyal. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

My Personal Notes arrow_drop_up