using System using System Collections Generic using System Linq using

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ConsoleApplication10
{
    class graph
    {
        private List<int> heads;
        private List<int> leafs = new List<int>(0);
        private const int empty = -1;
        private List<int> starts = new List<int>(0);
        private List<int> ends = new List<int>(0);

        private int _arcNumber = 0;

        private int getNewArcNumber()
        {
            int number = this._arcNumber;
            this._arcNumber++;
            leafs.Insert(number, -1);
            return number;
        }

        public graph(int nodeCount)
        {
            heads = new List<int>(nodeCount);
            for (int i = 0; i < nodeCount; i++)
            {
                heads.Add(empty);
            }
        }

        public void addArc(int start, int end)
        {
            Debug.Assert(start < heads.Count);
            Debug.Assert(end < heads.Count);

            int number = getNewArcNumber();
            starts.Insert(number, start);
            ends.Insert(number, end);

            leafs[number] = heads[start];
            heads[start] = number;
        }

        private int getArcNumber(int start, int end)
        {
            Debug.Assert(start < heads.Count);
            Debug.Assert(end < heads.Count);

            var index = starts.IndexOf(start);
            checkIndex(index);
            while (ends[index] != end)
            {
                index = starts.IndexOf(start, index + 1);
                checkIndex(index);
            }

            return index;
        }

        private void checkIndex(int index)
        {
            if (index < 0)
            {
                throw new Exception("Arc not found");
            }
        }

        public void printData()
        {
            printList(starts);
            printList(ends);
            printList(heads);
            printList(leafs);
        }

        private void printList(List<int> list)
        {
            foreach (var item in list)
            {
                Console.Write(item);
                Console.Write(" ");
            }
            Console.WriteLine();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var graph = new graph(4);
            graph.addArc(0, 1);
            graph.addArc(1, 2);
            graph.addArc(2, 3);
            graph.addArc(1, 3);
            graph.addArc(0, 2);
            graph.printData();
            Console.ReadKey();
        }
    }
}