Tutorialspoint.dev

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


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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter