loop in a graph

reference : geekforgeeks

Can be solved via set , or dfs and bfs.

set - looping over edges , when we encounter a edges whose any of the vertices have not been visited (are not present in set)  we insert them into the set.
whereas if we encounter a edge whose both the vertices already present in set,,,We have found a loop

the major problem we face for programming this through set or dfs or bfs is for the directed graph where we encounter both visited not but one happens to be the parent of other ,
so we should use a parent array for hashing keeping who is the parent of whom in our traversal and now if we encounter both visited we check if one is a immediate parent , and if that is the case we ignore it.

Bfs and dfs

bfs - if two nodes are connected at a level difference of more that 1 then there is a loop. we keep a record of level in traversal.

dfs - if we find a already visited node during traversal in dfs and that is not immediate parent of it , then its a loop

spoj question -- is it a tree 

set theory solution

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int main()
{
   // freopen("kr.in","r",stdin);
     /* scanf("%d",&t);
      while(t--)*/
      {
        set<int> s;
        int a,b;
        int flag=0;
        scanf("%d %d",&n,&m);
        if(n!=m+1)
            flag=1;
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            if(s.find(a)!=s.end() && s.find(b)!=s.end())
            {
                flag=1;
            }
            else
            {
                s.insert(a);
                s.insert(b);
            }
        }

        if(flag==1)
            printf("NO\n");
        else
            printf("YES\n");
       }
return 0;
}

dfs solution

#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

// should not be an immediate parent so i need a parent array

int parent[10000000];

int flag;

bool visited[1000000];

int dfs(vector<int> g[],int a,int n)

{ 

    stack <int > st;

    st.push(a);

    visited[a]=1;

    while(!st.empty())

    {

        int k=st.top();

        st.pop();

        for(int i=0;i<g[k].size();i++)

        {

            int V=g[k][i];

            if(!visited[V])

            {

                visited[V]=1;

                parent[V]=k;

                st.push(V);

            }

            else

            {

                if(parent[k]==V)

                {

                    continue;

                }

                flag=1;

               // printf("loop %d %d\n",k+1,V+1);

                return 0;

            }

        }

    }

}

int main()

{

int n,m;

//freopen("kr.in","r",stdin);

scanf("%d %d",&n,&m);

vector<int > g[n];

flag=0;

if(n-1!=m)

{

    printf("NO\n");

    return 0;

}

for(int i=0;i<m;i++)

{

    int a,b;

    scanf("%d %d",&a,&b);

    a--;b--;

    g[a].push_back(b);

    g[b].push_back(a);

}

//printf("sending dfs\n");

dfs(g,0,n);

for(int i=0;i<n;i++)

{

    if(!visited[i])

    {  // printf("not visited %d\n",i+1);

        flag=1;

        break;

    }

}

if(flag==1)

{

    printf("NO\n");

}

else{

    printf("YES\n");

}

}