Solution: Find All Connected Components in a Graph

class Program
{
    /// <summary>
    /// Method to find the connected components in a graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <returns>A list of connected components.</returns>
    public static List<List<int>> ConnectedComponents(Graph graph)
    {
        List<List<int>> result = new List<List<int>>();
        bool[] visited = new bool[graph.V];
        for (int v = 0; v < graph.V; v++)
        {
            if (!visited[v])
            {
                result.Add(DFS(graph, v, visited));
            }
        }
        return result;
    }
    // Helper method for DFS. Might be useful
    /// <summary>
    /// Method to print a DFS of a graph.
    /// </summary>
    /// <param name="graph">The graph.</param>
    /// <param name="source">Starting vertex.</param>
    static List<int> DFS(Graph g, int source, bool[] visited)
    {
        Graph graph = DeepCopyGraph(g);
        // Create a stack for DFS
        Stack<int> stack = new Stack<int>();
        // Result string
        List<int> result = new List<int>();
        // Push the source
        stack.Push(source);
        while (stack.Count > 0)
        {
            // Pop a vertex from stack
            source = stack.Pop();
            if (!visited[source])
            {
                result.Add(source);
                visited[source] = true;
            }
            AdjNode temp = graph.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 DeepCopyGraph(Graph g)
    {
        Graph newGraph = new Graph(g.V);
        for (int i = 0; i < g.V; i++)
        {
            newGraph.graph[i] = null;
            AdjNode temp = g.graph[i];
            while (temp != null)
            {
                newGraph.AddEdge(i, temp.Vertex);
                temp = temp.Next;
            }
        }
        return newGraph;
    }
    // Main program to test above method
    static void Main(string[] args)
    {
        Graph g = new Graph(7);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 3);
        g.AddEdge(3, 0);
        g.AddEdge(4, 5);
        g.AddEdge(5, 6);
        List<List<int>> result = ConnectedComponents(g);
        Console.WriteLine("Following are connected components");
        var sb = new System.Text.StringBuilder("[");
        for (var i = 0; i < result.Count; i++)
        {
            sb.Append("[" + string.Join(", ", result[i]) + "]");
            if (i < result.Count - 1)
                sb.Append(", ");
        }
        sb.Append("]");
        Console.WriteLine(sb.ToString());
    }
}