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 countint 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;}// Driverint 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 Codepublic 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 Codepublic 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 neveropen 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 neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
