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

// produces list representation of inverted graph 

// (where all edges have opposite directions with respect to original graph).

// The conversion time should be O(V+E) where V is the number of vertices and E is the number of edges.

using System;

public class Program

{

    public static int[][] Invert(int [][] edges)

    {

        int V = edges.Length;

        // pre-calculate number of incoming arrows for each vertex

        // to avoid re-allocations; time O(V+E)

        int [] leftToSet = new int[V];

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

        {

            foreach(int vertexTo in edges[vertexFrom])

            {

                leftToSet[vertexTo]++;

            }

        }

        // Allocate inverted graph

        int [][] inv = new int[V][];

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

        {

            inv[vertexTo] = new int[leftToSet[vertexTo]];

        }

        // Fill inverted graph

        // Invariant: for each vertexTo, last elements

        // of inv[vertexTo] array are filled with inverted edges,

        // and first leftToSet[vertexTo] elements are not filled yet

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

        {

            foreach(int vertexTo in edges[vertexFrom])

            {

                leftToSet[vertexTo]--;

                inv[vertexTo][leftToSet[vertexTo]] = vertexFrom;

            }

        }

        return inv;

    }

​

    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 [][] inv = Invert(edges);

        Print("Original graph", edges);

        Print("Inverted graph", inv);

    }

    private static void Print(string title, int [][] edges)

    {

        Console.WriteLine(title);

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

        {

            Console.Write("{0} ->", vertexFrom);

            foreach(int vertexTo in edges[vertexFrom])

            {

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

            }

            Console.WriteLine();

        }

    }

}