Skip to content
Related Articles

Related Articles

Count single node isolated sub-graphs in a disconnected graph

View Discussion
Improve Article
Save Article
  • Difficulty Level : Basic
  • Last Updated : 19 Jul, 2022
View Discussion
Improve Article
Save Article

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

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[7];
     
    // Representing edges
    graph[1] = 2;
    graph[2] = 1;
    graph[2] = 3;
    graph[3] = 2;
    graph[5] = 6;
    graph[6] = 5;
 
    Console.WriteLine(compute(graph, N));
}
}
 
// This code is contributed by 29AjayKumar

Javascript




<script>
 
// JavaScript code to count the singleton sub-graphs
// in a disconnected graph
 
// Function to compute the count
function compute(graph,N)
{
    // Storing intermediate result
    let count = 0;
       
    // Traversing the Nodes
    for (let i = 1; i < 7; i++)
    {
        // Singleton component
        if (graph[i].length == 0)
            count++;    
    }
           
    // Returning the result
    return count;
}
 
// Driver Code
// Number of nodes
let N = 6;
 
// Adjacency list for edges 1..6
let graph = new Array(7);
for(let i=0;i<7;i++)
{
    graph[i]=[];
}
// Representing edges
graph[1].push(2)
graph[2].push(1)
 
graph[2].push(3)
graph[3].push(2)
 
graph[5].push(6)
graph[6].push(5)
document.write(compute(graph, N));
 
// This code is contributed by rag2127
 
</script>

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
Recommended Articles
Page :

Start Your Coding Journey Now!