// Write a function that gets list representation of oriented graph and prints all vertices

// reachable from vertex 0 (any reachable vertex including vertex 0 should be printed once).

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 };

        for(int vertex = 0; vertex < edges.Length; vertex++)

        {

            Console.Write("Reachable from {0}: ", vertex);

            PrintReachable(edges, vertex);

            Console.WriteLine();

        }

    }

​

    private static void PrintReachable(int [][] edges, int vertexFrom)

    {

        int V = edges.Length;

        bool[] printed = new bool[V];

        Queue<int> reachableNotPrinted = new Queue<int>(V);

        reachableNotPrinted.Enqueue(vertexFrom);

        // Let's add "invisible" vertex with single edge leading to VertexFrom. Let's consider it printed.

        // Then the following invariant holds: 

        // The queue contains all not printed vertices reachable directly from already printed vertices

        while(reachableNotPrinted.Count > 0)

        {

            int vertex = reachableNotPrinted.Dequeue();

            Console.Write("{0} ", vertex);

            printed[vertex] = true;

            foreach(int vertexTo in edges[vertex])

            {

                if(!printed[vertexTo])

                    reachableNotPrinted.Enqueue(vertexTo);

            }

        }

        // Proof of performance:

        // each vertex is being removed from queue only once, so we process each outgoing edge just once

        // This gives us O(V+E) performance

    }

}