UVa 12356 - Army Buddies

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld%lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld%lld",a,b)
#define pf3(a,b,c) printf("lld%lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
main()
{
    long  n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        long i,l,r,right[100005]= {0},left[100005]= {0};
        for(i=1; i<=n; i++)
        {
            left[i]=i-1;
            right[i]=i+1;
        }
        left[1]=-1;
        right[n]=-1;
        for(i=1; i<=m; i++)
        {
            cin>>l>>r;
            left[right[r]]=left[l];
            if(left[l]!=-1)
                cout<<left[l]<<" ";
            else
                cout<<"* ";
            right[left[l]]=right[r];
            if(right[r]!=-1)
                cout<<right[r]<<endl;
            else
            {
                cout<<"*"<<endl;
            }

        }
        cout<<"-"<<endl;
    }
}

Detect a cycle using DFS

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld",a,b)
#define pf3(a,b,c) printf("lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
#define M 100005
long visited[M], cycle = 0;
vector<long> edge[M];
void visit( long p )
{
    if( visited[p] == 2 || cycle )
        return;
    // we won't process anything if we already have found a cycle
    if( visited[p] == 1 )
    {
        cycle = 1; // found cycle
        return;
    }

    visited[p] = 1;
    for(long i=0; i<edge[p].size(); i++)
        visit( edge[p][i] );
    visited[p] = 2;
}
main()
{
    long n,m,q;
    while(cin>>n>>m>>q)
    {
        long i,u,v;
        for(i=1; i<=m; i++)
        {
            cin>>u>>v;
            edge[u].push_back(v);
        }
        cycle=0;
        visit(q);
        if(cycle==1)
        {
            printf("yes\n");
        }
        else
            printf("no\n");
        for(i=1; i<=m; i++)
        {
            edge[i].clear();
            visited[i]=0;
        }
    }
}