Solution: Detect a Cycle in a Graph

class Program
{
    /// <summary>
    /// Detects a cycle in a given graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <returns>True if there is a cycle in the given graph, otherwise False.</returns>
    public static bool DetectCycle(Graph graph)
    {
        // visited list to keep track of the nodes that have been visited since the beginning of the algorithm
        bool[] visited = new bool[graph.V];
        // stack keeps track of the nodes which are part of the current recursive call
        bool[] myStack = new bool[graph.V];
        for (int node = 0; node < graph.V; node++)
        {
            // DFS 
            if (DetectCycleRecursive(graph, node, visited, myStack))
            {
                return true;
            }
        }
        return false;
    }
    /// <summary>
    /// Detects a cycle in a given graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <param name="node">A source vertex.</param>
    /// <param name="visited">A list to track visited nodes.</param>
    /// <param name="stack">A helper stack.</param>
    /// <returns>True if there is a cycle in the given graph, otherwise False.</returns>
    static bool DetectCycleRecursive(Graph graph, int node, bool[] visited, bool[] myStack)
    {
        // Node was already in recursion stack. Cycle found.
        if (myStack[node])
        {
            return true;
        }
        // It has been visited before this recursion
        if (visited[node])
        {
            return false;
        }
        // Mark current node as visited and
        // add to recursion stack
        visited[node] = true;
        myStack[node] = true;
        AdjNode head = graph.graph[node];
        while (head != null)
        {
            // Pick adjacent node and call it recursively
            int adjacent = head.Vertex;
            // If the node is visited again in the same recursion => Cycle found
            if (DetectCycleRecursive(graph, adjacent, visited, myStack))
            {
                return true;
            }
            head = head.Next;
        }
        // remove the node from the recursive call
        myStack[node] = false;
        return false;
    }
    // Main program to test the above code
    public static void Main(string[] args)
    {
        Graph g1 = new Graph(4);
        g1.AddEdge(0, 1);
        g1.AddEdge(1, 2);
        g1.AddEdge(1, 3);
        g1.AddEdge(3, 0);
        Graph g2 = new Graph(3);
        g2.AddEdge(0, 1);
        g2.AddEdge(1, 2);
        Console.WriteLine(DetectCycle(g1)); // Output: True
        Console.WriteLine(DetectCycle(g2)); // Output: False
    }
}