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

namespace ZZ_Zadania_Z_Kolokiwum_
{       //Zadanie 5
        //W algorytmie BFS kolejność przechodzenia
        //wierzchołków wyznacza pewne drzewo
        //wierzchołek a zwraca listę krawędzi:
        //pray( wierzchołek początkowy,wierzchołek końcowy)
        //drzew ..
        //Dla grafu jak na rysunku i wierzchołka 1 zwraca:
        //{(1,2) , (2,5), (2,3) , (3,4), (4,5);

    class Graf
    {
        public int początkowy;
        public int końcowy;

        public Graf(int wierzchołek, int sąsiad)
        {
            this.początkowy = wierzchołek;
            this.końcowy = sąsiad;
        }
        public override string ToString()
        {
            return "(" + (początkowy + 1) + ";" + (końcowy +1) + ")";
        }

    }
    class Program
    {
        public static List<List<int>> MacierzNaListe(int[,] tab)
        {
            List<List<int>> wynik = new List<List<int>>();
            for (int i = 0; i < tab.GetLength(0); i++)
            {
                wynik.Add(new List<int>());
                for (int j = 0; j < tab.GetLength(1); j++)
                {
                    if(tab[i,j] != 0)
                    {
                        wynik[i].Add(j);
                    }
                }
            }

            return wynik;
        }


        public static List<Graf> BFS(List<List<int>> graf)
        {
            int start = 0;
            Stack<int> kolejka = new Stack<int>();
            List<Graf> wyniki = new List<Graf>();
            kolejka.Push(start);
            bool[] odwiedzone = new bool[graf.Count];

            while (kolejka.Count != 0)
            {
                int pobrany = kolejka.Pop();

                if (odwiedzone[pobrany] == false)
                {
                    odwiedzone[pobrany] = true;

                    for (int i = 0; i < graf[pobrany].Count; i++)
                    {

                        int nastepny = graf[pobrany][graf[pobrany].Count - i - 1];
                        if (!odwiedzone[nastepny])
                        {
                            kolejka.Push(nastepny);
                            wyniki.Add(new Graf(pobrany, nastepny));
                        }
                    }


                }


            }
            return wyniki;
        }



        static void Main(string[] args)
        {                  //1  2  3  4  5 6
            int[,] tab ={   {0, 1, 0, 0, 1, 0},
                            {1, 0, 1, 0, 1, 0},
                            {0, 1, 0, 1, 0, 0},
                            {0, 0, 1, 0, 1, 1},
                            {1, 1, 0, 1, 0, 0},
                            {0, 0, 0, 1, 0 ,0} };


            List<List<int>> graf = MacierzNaListe(tab);
            List<Graf> lista = BFS(graf);
            foreach (var item in lista)
            {
                Console.Write(item + "->");


            }

            Console.ReadKey();

        }
    }
}