Solution: Check If a Graph Is Strongly Connected

class Program
{
    /// <summary>
    /// Method to print a DFS of a graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <param name="source">Starting vertex.</param>
    public static string DFS(Graph myGraph, int source)
    {
        // Initialize all the vertices as not visited
        int V = myGraph.graph.Length;
        bool[] visited = new bool[V];
        // Create a stack for DFS
        Stack<int> stack = new Stack<int>();
        // Result string
        string result = "";
        // Push the source
        stack.Push(source);
        while (stack.Count > 0)
        {
            // Pop a vertex from stack
            source = stack.Pop();
            if (!visited[source])
            {
                result += source;
                visited[source] = true;
            }
            AdjNode temp = myGraph.graph[source];
            // Get all adjacent vertices of the popped vertex source.
            // If a adjacent has not been visited, then push it
            while (temp != null)
            {
                int data = temp.Vertex;
                if (!visited[data])
                {
                    stack.Push(data);
                }
                temp = temp.Next;
            }
        }
        return result;
    }
    static Graph Transpose(Graph myGraph)
    {
        int V = myGraph.V;
        Graph newGraph = new Graph(V);
        for (int source = 0; source < V; source++)
        {
            AdjNode temp = myGraph.graph[source];
            while (temp != null)
            {
                int destination = temp.Vertex;
                newGraph.AddEdge(destination, source);
                temp = temp.Next;
            }
        }
        return newGraph;
    }
    /// <summary>
    /// Finds if the graph is strongly connected or not.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <returns>True if the graph is strongly connected, otherwise False.</returns>
    public static bool IsStronglyConnected(Graph graph)
    {
        // Step 1: Do DFS traversal starting from the first vertex.
        string result = DFS(graph, 0);
        // If DFS traversal doesn't visit all vertices, then return false
        if (graph.V != result.Length)
        {
            return false;
        }
        // Step 2: Create a reversed graph
        Graph graph2 = Transpose(graph);
        // Step 3: Do DFS for reversed graph starting from the first vertex.
        // Staring Vertex must be same starting point of first DFS
        result = DFS(graph2, 0);
        // If all vertices are not visited in second DFS, then return false
        if (graph2.V != result.Length)
        {
            return false;
        }
        return true;
    }
    // Main program to test the above code
    static void Main(string[] args)
    {
        int V = 5;
        Graph g1 = new Graph(V);
        g1.AddEdge(0, 1);
        g1.AddEdge(1, 2);
        g1.AddEdge(2, 3);
        g1.AddEdge(2, 4);
        g1.AddEdge(3, 0);
        g1.AddEdge(4, 2);
        Console.WriteLine(IsStronglyConnected(g1) ? "Yes" : "No");
        Graph g2 = new Graph(V);
        g2.AddEdge(0, 1);
        g2.AddEdge(1, 2);
        g2.AddEdge(2, 3);
        g2.AddEdge(2, 4);
        Console.WriteLine(IsStronglyConnected(g2) ? "Yes" : "No");
    }
}