detect cycle in an undirected graph c 2b 2b

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}