1// A C++ Program to detect
2// cycle in an undirected graph
3#include<iostream>
4#include <list>
5#include <limits.h>
6using namespace std;
7
8// Class for an undirected graph
9class Graph
10{
11
12 // No. of vertices
13 int V;
14
15 // Pointer to an array
16 // containing adjacency lists
17 list<int> *adj;
18 bool isCyclicUtil(int v, bool visited[],
19 int parent);
20public:
21
22 // Constructor
23 Graph(int V);
24
25 // To add an edge to graph
26 void addEdge(int v, int w);
27
28 // Returns true if there is a cycle
29 bool isCyclic();
30};
31
32Graph::Graph(int V)
33{
34 this->V = V;
35 adj = new list<int>[V];
36}
37
38void Graph::addEdge(int v, int w)
39{
40
41 // Add w to v’s list.
42 adj[v].push_back(w);
43
44 // Add v to w’s list.
45 adj[w].push_back(v);
46}
47
48// A recursive function that
49// uses visited[] and parent to detect
50// cycle in subgraph reachable
51// from vertex v.
52bool Graph::isCyclicUtil(int v,
53 bool visited[], int parent)
54{
55
56 // Mark the current node as visited
57 visited[v] = true;
58
59 // Recur for all the vertices
60 // adjacent to this vertex
61 list<int>::iterator i;
62 for (i = adj[v].begin(); i !=
63 adj[v].end(); ++i)
64 {
65
66 // If an adjacent vertex is not visited,
67 //then recur for that adjacent
68 if (!visited[*i])
69 {
70 if (isCyclicUtil(*i, visited, v))
71 return true;
72 }
73
74 // If an adjacent vertex is visited and
75 // is not parent of current vertex,
76 // then there exists a cycle in the graph.
77 else if (*i != parent)
78 return true;
79 }
80 return false;
81}
82
83// Returns true if the graph contains
84// a cycle, else false.
85bool Graph::isCyclic()
86{
87
88 // Mark all the vertices as not
89 // visited and not part of recursion
90 // stack
91 bool *visited = new bool[V];
92 for (int i = 0; i < V; i++)
93 visited[i] = false;
94
95 // Call the recursive helper
96 // function to detect cycle in different
97 // DFS trees
98 for (int u = 0; u < V; u++)
99 {
100
101 // Don't recur for u if
102 // it is already visited
103 if (!visited[u])
104 if (isCyclicUtil(u, visited, -1))
105 return true;
106 }
107 return false;
108}
109
110// Driver program to test above functions
111int main()
112{
113 Graph g1(5);
114 g1.addEdge(1, 0);
115 g1.addEdge(0, 2);
116 g1.addEdge(2, 1);
117 g1.addEdge(0, 3);
118 g1.addEdge(3, 4);
119 g1.isCyclic()?
120 cout << "Graph contains cycle\n":
121 cout << "Graph doesn't contain cycle\n";
122
123 Graph g2(3);
124 g2.addEdge(0, 1);
125 g2.addEdge(1, 2);
126 g2.isCyclic()?
127 cout << "Graph contains cycle\n":
128 cout << "Graph doesn't contain cycle\n";
129
130 return 0;
131}