Cycle Detection in Undirected Graph Code

Raunit Verma June 21, 2022

Cycle Detection in Undirected Graph Code

#include <bits/stdc++.h>
using namespace std;

class Graph
{
    list<int> *l;
    int v;

public:
    Graph(int v)
    {
        this->v = v+1;
        l = new list<int>[v+1];
    }

    void addEdge(int x, int y)
    {
        l[x].push_back(y);
        l[y].push_back(x);
    }

    bool dfs(int node, vector<bool> &visited, int parent)
    {
        visited[node] = true;
        for (auto nbr : l[node])
        {
            if (!visited[nbr])
            {
                bool foundCycle = dfs(nbr, visited, node);
                if (foundCycle)
                    return true;
            }
            // nbr is visited and its not the parent of the current node
            else if (visited[nbr] && nbr != parent)
                return true;
        }
        return false;
    }

    bool constainCycle()
    {

        vector<bool> visited(v, false);
        if (dfs(0, visited, -1))
            return true;
        return false;
    }
};

int main()
{
    Graph g(5);
    g.addEdge(0,1);
    g.addEdge(1,2);
    g.addEdge(2,3);
    g.addEdge(4,0);
    g.addEdge(4,5);
    g.addEdge(0,5);
    cout<<g.constainCycle();
    return 0;
}