using System using System Collections Generic using System Linq using

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.IO;

namespace ShortestWaySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            BundleRelationGraph graph = new BundleRelationGraph();
            graph.AddRelation(0, 1);
            graph.AddRelation(1, 2);
            graph.AddRelation(2, 0);
            graph.AddRelation(1, 0);
            graph.AddRelation(2, 3);
            graph.AddRelation(0, 3);
            graph.AddRelation(0, 4);
            graph.AddRelation(4, 0);
            graph.AddRelation(4, 3);
            printList(graph.W);
            printList(graph.L);
            printList(graph.J);
            printList(graph.getShortestWayTreeFor(0));
            File.WriteAllText("C:\\Users\\11\\Links\\output.txt", "Graph:" + graph.getIJFormatedText() + "Tree:" + graph.getIJFormatedTreeTextFor(0));
            Console.WriteLine(graph.getIJFormatedText());
            Console.WriteLine();
            Console.WriteLine(graph.getIJFormatedTreeTextFor(0));
            Console.ReadKey();
        }

        static void printList(List<int> lst)
        {
            for (int i = 0; i < lst.Count; i++)
            {
                Console.Write(" " + lst[i]);
            }
            Console.WriteLine();
        }
    }

    class BundleRelationGraph
    {
        public List<int> W;
        public List<int> L;
        public List<int> J;


        public BundleRelationGraph()
        {
            W = new List<int>();
            L = new List<int>();
            J = new List<int>();
        }

        private void RestructBundlesFor(int vertNum)
        {
            Debug.Assert(vertNum < W.Count);
            if (W[vertNum] < 0)
            {
                W[vertNum] = L.Count - 1;
            }
            else
            {
                int j = W[vertNum];
                while (L[j] >= 0)
                {
                    j = L[j];
                }
                L[j] = L.Count - 1;
            }
        }

        public string getIJFormatedText()
        {
            string text = "";
            for (int i = 0; i < W.Count; i++)
            {
                if (W[i] >= 0)
                {
                    int j = W[i];
                    while (j >= 0)
                    {
                        text += i + " -> " + J[j] + " ";
                        j = L[j];
                    }
                }
            }
            return text;
        }

        public string getIJFormatedTreeTextFor(int vertNum)
        {
            Debug.Assert(vertNum < W.Count);
            string text = "";
            List<int> parentTree = this.getShortestWayTreeFor(vertNum);
            for (int i = 1; i < parentTree.Count; i++)
            {
                text += i + " -> " + parentTree[i] + " ";
            }
            return text;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="i">from vertex</param>
        /// <param name="j">to vertex</param>
        public void AddRelation(int i, int j)
        {
            L.Add(-1);
            if (i < W.Count)
            {
                RestructBundlesFor(i);
            }
            else
            {
                W.Add(L.Count - 1);
            }

            if (j >= W.Count)
            {
                W.Add(-1);
            }
            J.Add(j);
        }

        public List<int> getShortestWayTreeFor(int relNum)
        {
            Debug.Assert(W.Count > relNum);
            List<int> parentList = new List<int>(W.Count);
            Queue<int> Q = new Queue<int>(W.Count);
            Queue<int> S = new Queue<int>(W.Count);
            List<int> Ri = new List<int>(W.Count);
            Q.Enqueue(relNum);
            for (int i = 0; i < W.Count; i++)
            {
                Ri.Add((relNum == i) ? 0 : int.MaxValue);
                parentList.Add(-1);
            }

            while (Q.Count > 0)
            {
                int rel = Q.Dequeue();
                int j = W[rel];
                while (j >= 0 && !S.Contains(rel))
                {
                    int destRel = J[j];
                    if (!Q.Contains(destRel) && !S.Contains(destRel))
                    {
                        Q.Enqueue(destRel);
                        parentList[destRel] = rel;
                        Ri[destRel] = Ri[rel] + 1;
                    }
                    j = L[j];
                }
                S.Enqueue(rel);
            }
            return parentList;
        }
    }
}