// Write a function that checks whether there are any cycles in oriented graph represented by adjacency list.

// Time should be O(V+E) where V is number of vertices and E is number of edges.

using System;

using System.Collections.Generic;

​

public class Program

{

    public static void Main()

    {

        int[][] edges = new int[5][];

        edges[0] = new int[] { 1, 4 };

        edges[1] = new int[] { 3 };

        edges[2] = new int[] { 4 };

        edges[3] = new int[] { 4 };

        edges[4] = new int[] { 0 };

        int[] pathWithLoop = FindLoop(edges);

        if(null == pathWithLoop)

        {

            Console.WriteLine("No loops found");

        }

        else

        {   // Path might contain pre-loop segment, skip it

            int loopVertex = pathWithLoop[pathWithLoop.Length - 1];

            int start = 0;

            while(pathWithLoop[start] != loopVertex)

                start++;

            Console.Write("Loop found: {0}", loopVertex);

            for(int i = start+1; i < pathWithLoop.Length; i++)

            {

                Console.Write(" -> {0}", pathWithLoop[i]);

            }

            Console.WriteLine();

        }

    }

​

    // Returns array with the path containing loop at the end in case there is a loop

    // Returns null if there are no loops in this graph

    private static int[] FindLoop(int [][] edges)

    {

        int V = edges.Length;

        int[] edgesChecked = new int[V];

​

        // Invariant: any edge[vertex][i] where i < edgesChecked[vertex] cannot be part of a loop

        for(int vertexFrom = 0; vertexFrom < V; vertexFrom++)

        {

            if(edgesChecked[vertexFrom] < edges[vertexFrom].Length)

            {   // investigate the path going through the first unchecked edge

                Stack<int> reachableFrom = new Stack<int>(V);

                bool[] inStack   = new bool[V];

                // Invariant:

                // reachableFrom contains a path going from vertexFrom and coming through the 1st unchecked edge through each vertex

                // Limiter: the pair (number of unchecked edges, pathLength) is being decreased lexicographically

                reachableFrom.Push(vertexFrom);

                inStack[vertexFrom] = true;

                while(reachableFrom.Count > 0)

                {

                    int vertex = reachableFrom.Peek();

                    if(edgesChecked[vertex] < edges[vertex].Length)

                    {   // there is unchecked edge, check it.

                        int nextVertex = edges[vertex][edgesChecked[vertex]];

                        reachableFrom.Push(nextVertex);

                        if(inStack[nextVertex])

                        {   // we have a loop, return it

                            return reachableFrom.ToArray();

                        }

                    }

                    else

                    {   // all forward pathes are checked, go back and check other forks

                        reachableFrom.Pop();

                        inStack[vertex] = false;

                        if(reachableFrom.Count > 0)

                        {

                            int previousVertex = reachableFrom.Peek();

                            edgesChecked[previousVertex]++;  // we didn't find loops via this edge

                        }

                    }

                }

            }

        }

        return null;

    }

}

​