Detecting and printing a cycle from a Graph

The question is to detect and print any cycle, if exists, in a given graph else print -1.The question was asked by Amazon during on-campus recruitment coding round.

Algorithm:

The question can be solved using Depth First Search.Existence of cycle can be easily detected if we again reach an element which was already visited.

Input

The very first line denotes number of nodes,N, in a given graph.Following lines will contain two inputs, s and d, which signifies that there is a directed edge from node s to node d.The inputs will terminate at -1.

Output

We have to output the edges forming any one of the cycle in the format s->d.Every edge should occupy new line.

Constraints
1<=N<=10000

example:

input                           output
4                                 1->2
1 2                              2->4
2 4                              4->3
1 4                              3->1
4 3
3 1
-1

See the graph image.Red edges are the provided directed edges.While yellow edges are those which form a cycle.

Implementation:

/*
Problem Description: Detect and print a cycle from a graph

Submitted By:
Arjun Mishra
*/

#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#define MAX 100001
vector<int> AdjList[MAX];
int N;//no of nodes
int mark;//mark is the node which is repeated
//function to find whether cycle exists or not, it is nothing but dfs implementation
int findCycle(int visited[MAX],int level,int output[MAX],int *index)
{
if(level>N)
return 0;
int l=AdjList[level].size(),i;
for(i=0;i<l;i++)
{
if(!visited[AdjList[level][i]])//if the node is visited for the first time
{
visited[AdjList[level][i]]=1;
output[(*index)++]=AdjList[level][i];
return findCycle(visited,AdjList[level][i],output,index);
}
else//if the node already is visited
{
mark=AdjList[level][i];
return 1;//condition is true as cycle detected
}
}
return 0;//no cycle found
}
//driver utility
int main()
{
int i;
cin>>N;
while(1)
{
int a,b;
cin>>a;
if(a==-1)
break;
cin>>b;
AdjList[a].push_back(b);//maintaining adjacency list
}

for(i=1;i<=N;i++)
{
int output[MAX],visited[MAX]={},*index,flag=0,s=0;
index=&s;
visited[i]=1;
output[*index]=i;
*index=(*index)+1;
flag=findCycle(visited,i,output,index);//calling findCycle utility
if(flag)//printing cycle if flag==1, meaning cycle detected
{
int f=0,j;
//printing the cycle
for(j=0;j<(*index)-1;j++)
{
if(output[j]==mark)
{
f=1;
}
if(f)
printf("%d->%d\n",output[j],output[j+1]);
}
printf("%d->%d\n",output[j],mark);

printf("\n");
//exit
return 0;
}
}
printf("-1\n");//no cycle detected
//end of program
return 0;
}