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 a 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 a 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 verticesint degree[N];// to keep track of all the vertices covered // till nowbool found[N];// all the vertices in a particular // connected component of the graphvector<int> curr_graph;// adjacency listvector<int> adj_list[N];// depth-first traversal to identify all the// nodes in a particular connected graph // componentvoid 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 graphvoid 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;} |
Java
// Java program to find single cycle components // in a graph. import java.util.*;class GFG{static int N = 100000; // degree of all the vertices static int degree[] = new int[N]; // to keep track of all the vertices covered // till now static boolean found[] = new boolean[N]; // all the vertices in a particular // connected component of the graph static Vector<Integer> curr_graph = new Vector<Integer>(); // adjacency list static Vector<Vector<Integer>> adj_list = new Vector<Vector<Integer>>(); // depth-first traversal to identify all the // nodes in a particular connected graph // component static void DFS(int v) { found[v] = true; curr_graph.add(v); for (int it = 0 ;it < adj_list.get(v).size(); it++) if (!found[adj_list.get(v).get(it)]) DFS(adj_list.get(v).get(it)); } // function to add an edge in the graph static void addEdge( int src,int dest) { // for index decrement both src and dest. src--; dest--; adj_list.get(src).add(dest); adj_list.get(dest).add(src); degree[src]++; degree[dest]++; } static 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 = 0 ; v < curr_graph.size(); v++) { if (degree[curr_graph.get(v)] == 2) continue; else { flag = 0; break; } } if (flag == 1) { count++; } } } return(count); } // Driver codepublic static void main(String args[]){ for(int i = 0; i < N + 1; i++) adj_list.add(new Vector<Integer>()); // n->number of vertices // m->number of edges int n = 15, m = 14; addEdge( 1, 10); addEdge( 1, 5); addEdge( 5, 10); addEdge( 2, 9); addEdge( 9, 15); addEdge( 2, 15); addEdge( 2, 12); addEdge( 12, 15); addEdge( 13, 8); addEdge( 6, 14); addEdge( 14, 3); addEdge( 3, 7); addEdge( 7, 11); addEdge( 11, 6); System.out.println(countSingleCycles(n, m)); }} // This code is contributed by Arnab Kundu |
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] += 1def 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 Codeif __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 |
C#
// C# program to find single cycle components // in a graph. using System;using System.Collections.Generic; class GFG{static int N = 100000; // degree of all the vertices static int []degree = new int[N]; // to keep track of all the vertices covered // till now static bool []found = new bool[N]; // all the vertices in a particular // connected component of the graph static List<int> curr_graph = new List<int>(); // adjacency list static List<List<int>> adj_list = new List<List<int>>(); // depth-first traversal to identify all the // nodes in a particular connected graph // component static void DFS(int v) { found[v] = true; curr_graph.Add(v); for (int it = 0; it < adj_list[v].Count; it++) if (!found[adj_list[v][it]]) DFS(adj_list[v][it]); } // function to add an edge in the graph static void addEdge(int src,int dest) { // for index decrement both src and dest. src--; dest--; adj_list[src].Add(dest); adj_list[dest].Add(src); degree[src]++; degree[dest]++; } static 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 = 0 ; v < curr_graph.Count; v++) { if (degree[curr_graph[v]] == 2) continue; else { flag = 0; break; } } if (flag == 1) { count++; } } } return(count); } // Driver codepublic static void Main(String []args){ for(int i = 0; i < N + 1; i++) adj_list.Add(new List<int>()); // n->number of vertices // m->number of edges int n = 15, m = 14; addEdge(1, 10); addEdge(1, 5); addEdge(5, 10); addEdge(2, 9); addEdge(9, 15); addEdge(2, 15); addEdge(2, 12); addEdge(12, 15); addEdge(13, 8); addEdge(6, 14); addEdge(14, 3); addEdge(3, 7); addEdge(7, 11); addEdge(11, 6); Console.WriteLine(countSingleCycles(n, m)); }} // This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to find single cycle components // in a graph. let N = 100000; // degree of all the vertices let degree=new Array(N);for(let i=0;i<N;i++) degree[i]=0;// to keep track of all the vertices covered // till now let found=new Array(N);for(let i=0;i<N;i++) found[i]=0;// all the vertices in a particular // connected component of the graph let curr_graph = [];// adjacency list let adj_list = [];// depth-first traversal to identify all the // nodes in a particular connected graph // component function DFS(v){ found[v] = true; curr_graph.push(v); for (let it = 0 ;it < adj_list[v].length; it++) if (!found[adj_list[v][it]]) DFS(adj_list[v][it]); }// function to add an edge in the graph function addEdge(src,dest){ // for index decrement both src and dest. src--; dest--; adj_list[src].push(dest); adj_list[dest].push(src); degree[src]++; degree[dest]++; }function countSingleCycles(n,m){ // count of cycle graph components let count = 0; for (let i = 0; i < n; ++i) { if (!found[i]) { curr_graph=[]; DFS(i); // traversing the nodes of the // current graph component let flag = 1; for (let v = 0 ; v < curr_graph.length; v++) { if (degree[curr_graph[v]] == 2) continue; else { flag = 0; break; } } if (flag == 1) { count++; } } } return(count); }// Driver codefor(let i = 0; i < N + 1; i++) adj_list.push([]);// n->number of vertices // m->number of edges let n = 15, m = 14; addEdge( 1, 10); addEdge( 1, 5); addEdge( 5, 10); addEdge( 2, 9); addEdge( 9, 15); addEdge( 2, 15); addEdge( 2, 12); addEdge( 12, 15); addEdge( 13, 8); addEdge( 6, 14); addEdge( 14, 3); addEdge( 3, 7); addEdge( 7, 11); addEdge( 11, 6); document.write(countSingleCycles(n, m)); // This code is contributed by avanitrachhadiya2155</script> |
Output:
2
Time Complexity: O(N+M) where N is the number of vertices and M is the number of edges in the graph.
Auxiliary Space: O(N + M)
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!
