bfsdfs.cpp

#include<bits/stdc++.h>
using namespace std;
#define MAX 2000005
class Graph
{
    vector<int>g[MAX];
    int color[MAX];
    long long  in[MAX];
    long long  out[MAX];
    int edges;
    int t;
    int parent[MAX];
    bool directed;
    long long dist[MAX];
    int vertics;
public:
    Graph(int n,bool dir=false)
    {
        this->vertics=n;
        this->edges=0;
        for(int i=0; i<n; i++)
        {
            t=0;
            g[i].clear();
            color[i]=0;
            in[i]=-1;
            out[i]=-1;
            parent[i]=-1;
            dist[i]=-1;
        }
        this->directed=dir;

    }
    void addEdge(int u,int v)
    {
        this->edges++;
        this->g[u].push_back(v);
        if(!directed)
        {
            this->g[v].push_back(u);
        }
    }
    void removeEdge(int u,int v)
    {
        this->edges--;
        vector<int>::iterator it=find(g[u].begin(),g[u].end(),v);
        g[u].erase(it);
        if(!directed)
        {
            it=find(g[v].begin(),g[v].end(),u);
            g[v].erase(it);
        }

    }
    void Set()
    {
        t=0;
        for(int i=0; i<vertics; i++)
        {
            g[i].clear();
            color[i]=0;
            in[i]=-1;
            out[i]=-1;
            parent[i]=-1;
            dist[i]=-1;
        }
    }
    void bfs(int source)
    {
        color[source]=1;
        dist[source]=0;
        queue<int>q;
        q.push(source);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int i=0; i<g[u].size(); i++)
            {
                int v=g[u][i];
                if(color[v]==0)
                {
                    dist[v]=dist[u]+1;
                    color[v]=1;
                    q.push(v);
                    parent[v]=u;
                }
            }
            color[u]=2;
        }

    }
    long long distance(int u,int v)
    {
        Set();
        bfs(u);
        return dist[v];
    }
    void dfs(int source)
    {

        in[source]=t++;
        color[source]=1;
        for(int i=0; i<g[source].size(); i++)
        {
            if(color[g[source][i]]==0)
            {
                dfs(g[source][i]);

            }
        }

        out[source]=t++;

    }
    int  isconnected()
    {
        Set();
        int co=0;
        for(int i=0; i<vertics; i++)
        {

            if(color[i]==0)
            {

                dfs(i);
                co++;
            }
        }
        return co;

    }
    bool dfs2(int source)
    {
        if(color[source]==1) return true;

        color[source]=1;
        for(int i=0; i<g[source].size(); i++)
        {
            if(color[g[source][i]]==0)
            {
                dfs(g[source][i]);
            }
        }
        color[source]=2;
        return false;
    }
    bool cycle()
    {
        Set();
        return dfs2(0);
    }
    void printpath(int u)
    {
        stack<int>s;
        s.push(u);
        while(parent[u]!=-1)
        {
            s.push(parent[u]);
            u=parent[u];
        }
        while(!s.empty())
        {
            printf("%d ",s.top());
            s.pop();
        }
        printf("\n");
    }
    bool isDescendent(int x, int y)
    {
        return (in[x] <= in[y] && out[x] >= out[y]);
    }
    bool isAscendent(int x, int y)
    {
        return (in[x] >= in[y] && out[x] <= out[y]);
    }


};
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y;
    Graph g(n);
    for(int i=0;i<m;i++){
        cin>>x>>y;
        g.addEdge(x,y);
    }
    if(g.isconnected()){
        cout<<"Connected graph"<<endl;
    }
    else cout<<"Not a connected graph"<<endl;
    if(g.cycle()){
        cout<<"Having cycle"<<endl;
    }
    else cout<<"Not having a cycle"<<endl;
    g.bfs(0);
    g.printpath(0);//take input for which you need to print the path
    cout<<g.distance(1,2);//take input two numbers
    g.dfs(0);




}