Given a set of ‘n’ vertices and ‘m’ edges of an undirected simple graph (no parallel edges and no self-loop), find the number of single-cycle-components present in the graph. A single-cyclic-component is a graph of n nodes containing a single cycle through all nodes of the component.
Example:
Let us consider the following graph with 15 vertices.Input: V = 15, E = 14 1 10 // edge 1 1 5 // edge 2 5 10 // edge 3 2 9 // .. 9 15 // .. 2 15 // .. 2 12 // .. 12 15 // .. 13 8 // .. 6 14 // .. 14 3 // .. 3 7 // .. 7 11 // edge 13 11 6 // edge 14 Output :2 In the above-mentioned example, the two single-cyclic-components are composed of vertices (1, 10, 5) and (6, 11, 7, 3, 14) respectively.
Now we can easily see that a single-cycle-component is a connected component where every vertex has the degree as two.
Therefore, in order to solve this problem we first identify all the connected components of the disconnected graph. For this, we use depth-first search algorithm. For the DFS algorithm to work, it is required to maintain an array ‘found’ to keep an account of all the vertices that have been discovered by the recursive function DFS. Once all the elements of a particular connected component are discovered (like vertices(9, 2, 15, 12) form a connected graph component ), we check if all the vertices in the component are having the degree equal to two. If yes, we increase the counter variable ‘count’ which denotes the number of single-cycle-components found in the given graph. To keep an account of the component we are presently dealing with, we may use a vector array ‘curr_graph’ as well.
C++
// CPP program to find single cycle components // in a graph. #include <bits/stdc++.h> using namespace std; const int N = 100000; // degree of all the vertices int degree[N]; // to keep track of all the vertices covered // till now bool found[N]; // all the vertices in a particular // connected component of the graph vector<int> curr_graph; // adjacency list vector<int> adj_list[N]; // depth-first traversal to identify all the // nodes in a particular connected graph // component void DFS(int v) { found[v] = true; curr_graph.push_back(v); for (int it : adj_list[v]) if (!found[it]) DFS(it); } // function to add an edge in the graph void addEdge(vector<int> adj_list[N], int src, int dest) { // for index decrement both src and dest. src--, dest--; adj_list[src].push_back(dest); adj_list[dest].push_back(src); degree[src]++; degree[dest]++; } int countSingleCycles(int n, int m) { // count of cycle graph components int count = 0; for (int i = 0; i < n; ++i) { if (!found[i]) { curr_graph.clear(); DFS(i); // traversing the nodes of the // current graph component int flag = 1; for (int v : curr_graph) { if (degree[v] == 2) continue; else { flag = 0; break; } } if (flag == 1) { count++; } } } return(count); } int main() { // n->number of vertices // m->number of edges int n = 15, m = 14; addEdge(adj_list, 1, 10); addEdge(adj_list, 1, 5); addEdge(adj_list, 5, 10); addEdge(adj_list, 2, 9); addEdge(adj_list, 9, 15); addEdge(adj_list, 2, 15); addEdge(adj_list, 2, 12); addEdge(adj_list, 12, 15); addEdge(adj_list, 13, 8); addEdge(adj_list, 6, 14); addEdge(adj_list, 14, 3); addEdge(adj_list, 3, 7); addEdge(adj_list, 7, 11); addEdge(adj_list, 11, 6); cout << countSingleCycles(n, m); return 0; } |
Python3
# Python3 program to find single
# cycle components in a graph.
N = 100000
# degree of all the vertices
degree = [0] * N
# to keep track of all the
# vertices covered till now
found = [None] * N
# All the vertices in a particular
# connected component of the graph
curr_graph = []
# adjacency list
adj_list = [[] for i in range(N)]
# depth-first traversal to identify
# all the nodes in a particular
# connected graph component
def DFS(v):
found[v] = True
curr_graph.append(v)
for it in adj_list[v]:
if not found[it]:
DFS(it)
# function to add an edge in the graph
def addEdge(adj_list, src, dest):
# for index decrement both src and dest.
src, dest = src – 1, dest – 1
adj_list[src].append(dest)
adj_list[dest].append(src)
degree[src] += 1
degree[dest] += 1
def countSingleCycles(n, m):
# count of cycle graph components
count = 0
for i in range(0, n):
if not found[i]:
curr_graph.clear()
DFS(i)
# traversing the nodes of the
# current graph component
flag = 1
for v in curr_graph:
if degree[v] == 2:
continue
else:
flag = 0
break
if flag == 1:
count += 1
return count
# Driver Code
if __name__ == “__main__”:
# n->number of vertices
# m->number of edges
n, m = 15, 14
addEdge(adj_list, 1, 10)
addEdge(adj_list, 1, 5)
addEdge(adj_list, 5, 10)
addEdge(adj_list, 2, 9)
addEdge(adj_list, 9, 15)
addEdge(adj_list, 2, 15)
addEdge(adj_list, 2, 12)
addEdge(adj_list, 12, 15)
addEdge(adj_list, 13, 8)
addEdge(adj_list, 6, 14)
addEdge(adj_list, 14, 3)
addEdge(adj_list, 3, 7)
addEdge(adj_list, 7, 11)
addEdge(adj_list, 11, 6)
print(countSingleCycles(n, m))
# This code is contributed by Rituraj Jain
2
Hence, total number of cycle graph component is found.
leave a comment
0 Comments