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

//Przeszukiwanie grafu w glab
//Autor: Mateusz Zaborowski 
//www.algorytm.org
namespace ConsoleApplication5
{
    class Program
    {
        static List<int> DFS(int[][] tab, int start)
        {
            int wierzcholekStart = start - 1;
            Stack<int> stos = new Stack<int>(); //stos
            List<int> listaWynikow = new List<int>();
            stos.Push(wierzcholekStart);    //dodanie pierwszego wierzcholka
            bool[] odwiedzoneWierzcholki = new bool[tab.Length];

            while (stos.Count!=0)
            {
                int pobranyWierzcholek = stos.Pop();
                if (odwiedzoneWierzcholki[pobranyWierzcholek] == false)
                {
                    odwiedzoneWierzcholki[pobranyWierzcholek]=true;
                    for (int i = (tab[pobranyWierzcholek].Length - 1); i>=0; i--)
                    {
                        if(tab[pobranyWierzcholek][i]!=0)
                        {
                            stos.Push(i);
                        }
                    }
                    listaWynikow.Add(pobranyWierzcholek);
                }
            }
            return listaWynikow;
        }
        static void Main(string[] args)
        {
            //(odczyt z dnia 2013.02.03)Przykład ze strony: http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html
            //DFS
            int[][] tab= {new int[] {0, 1, 1, 0, 0, 0},
                          new int[] {0, 0, 0, 1, 1, 0},
                          new int[] {0, 0, 0, 1, 0, 1},
                          new int[] {1, 0, 0, 0, 0, 0},
                          new int[] {0, 0, 0, 1, 0, 0},
                          new int[] {0, 0, 0, 0, 0, 0}};

            List<int> wynik=DFS(tab,1);
            Console.WriteLine("DFS\n");
            foreach (int wypisz in wynik)
            {
                Console.WriteLine((wypisz+1));
            }
            Console.ReadLine();
        }
    }
}