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.
leave a comment
0 Comments