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

namespace Euler
{

    class Graf
    {
        private int liczbaWierzcholkow;
        private int liczbaKrawedzi;
        private static int wielkosc=10;
        public static List<int>[] lista = new List<int>[wielkosc];
        public bool[] odwiedzony = new bool[lista.Length + 1];

        public Graf()
        {
            liczbaWierzcholkow = 0;
            liczbaKrawedzi = 0;
        }

        public void zbudujGraf()
        {
            Console.WriteLine("Podaj ilosc wierzcholkow: ");
            liczbaWierzcholkow = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Podaj ilosc krawedzi: ");
            liczbaKrawedzi = Convert.ToInt32(Console.ReadLine());

            for (int i = 0; i <= liczbaWierzcholkow; i++)
                lista[i] = new List<int>();

            for (int i = 1; i <= liczbaKrawedzi; i++)
            {
                int w1, w2;
                Console.WriteLine("Krawędź: " + i + ": ");
                w1 = Convert.ToInt32(Console.ReadLine());
                w2 = Convert.ToInt32(Console.ReadLine());

                lista[w1].Add(w2);
                lista[w2].Add(w1);
            }
            zapiszGraf();
            Console.WriteLine();
        }

        public void dodajKrawędź(int w1, int w2)
        {
            if (lista[w1].Count == 0)
                liczbaWierzcholkow++;

            if (lista[w2].Count == 0)
                liczbaWierzcholkow++;

            lista[w1].Add(w2);
            lista[w2].Add(w1);
            liczbaKrawedzi++;
        }

        public void usuńKrawędź(int w1, int w2)
        {
            bool czyUsunieto = false;

            if (lista[w1].Count != 0)
            {
                lista[w1].Remove(w2);
                lista[w2].Remove(w1);
                czyUsunieto = true;
            }

            if (czyUsunieto == true)
            {
                Console.WriteLine("Usunieto krawedz: "+ w1 + " -> " + w2);
                if (lista[w1].Count == 0)
                    liczbaWierzcholkow--;

                if (lista[w2].Count == 0)
                    liczbaWierzcholkow--;

                liczbaKrawedzi--;
            }
            else
                Console.WriteLine("Blad usuwania krawedzi! Podana krawedz " + w1 + " -> " + w2 + " nie istnieje.");

            zapiszGraf();
            Console.WriteLine();
        }

        public void wyświetlListęSąsiadów()
        {
            if (liczbaWierzcholkow == 0)
                Console.WriteLine("Graf jest pusty!");
            else
            {
                Console.WriteLine("Lista sasiedztwa wyglada nastepujaco: ");
                for (int i = 1; i < liczbaWierzcholkow + 1; i++)
                {
                    Console.Write("Wierzcholek " + i + ": ");

                    for (int j = 0; j < lista[i].Count; j++)
                    {
                        if (j != lista[i].Count - 1)
                            Console.Write(lista[i][j] +  ", ");
                        else
                            Console.WriteLine(lista[i][j] + " ");
                    }
                }
            }
            Console.WriteLine();
        }

        public void zapiszGraf()
        {
            StreamWriter zapisz = new StreamWriter("wyniki.txt");

            if (liczbaWierzcholkow == 0)
                Console.Write("Graf jest pusty!");
            else
                for (int i = 1; i < liczbaWierzcholkow + 1; i++)
                    for (int j = 0; j < lista[i].Count; j++)
                            zapisz.WriteLine(i + " " + lista[i][j]);
            zapisz.Close();
        }

        public void wczytajGraf()
        {
            StreamReader odczytaj = new StreamReader("wyniki.txt");
            string[] dane = new string[10];
            int liczbaLinii = 0;

            if (File.Exists("wyniki.txt"))
            {
                foreach (string line in File.ReadLines("wyniki.txt"))
                {
                    if (line != String.Empty)
                        liczbaLinii++;
                }

                for (int i = 0; i < liczbaLinii; i++)
                    dane[i] = odczytaj.ReadLine();

                for (int i = 0; i <= liczbaLinii; i++)
                    lista[i] = new List<int>();

                for (int i = 0; i < liczbaLinii; i++)
                {
                    int w1, w2;
                    w1 = Convert.ToInt32(dane[i].Substring(0, dane[i].IndexOf(" ")));
                    w2 = Convert.ToInt32(dane[i].Substring(dane[i].IndexOf(" ")));
                    if (lista[w1].Count == 0)
                        liczbaWierzcholkow++;

                    lista[w1].Add(w2);
                    liczbaKrawedzi++;
                }
            }
            else
                Console.WriteLine("Nie można wczytać grafu! Nie zapisano żadnych krawędzi grafu.");

            odczytaj.Close();
            Console.WriteLine();
        }

        public void DFSHelper(int start, bool[] odwiedzony)
        {
            odwiedzony[start] = true;
            Console.Write(start + "->");
            if (lista[start] != null)
                foreach (var element in lista[start])
                    if (!odwiedzony[element] == true)
                        DFSHelper(element, odwiedzony);
        }

        public void DFS(int wierzcholekStart)
        {
            Console.WriteLine("DFS");
            DFSHelper(wierzcholekStart, odwiedzony);
        }

        public int s=0;
        public void Euler(int wierzcholekStart)
        {
            int[,] cykl = new int[wielkosc,wielkosc];
            int[] wypiszCykl = new int[wielkosc];

            for (int i = 1; i < liczbaWierzcholkow + 1; i++)
                for (int j = 0; j < lista[i].Count; j++)
                    cykl[i,j] = lista[i][j];

            for (int i = 0; i < liczbaWierzcholkow; i++)
            {
                if (lista[i].Count % 2 != 0)
                {
                    Console.WriteLine("Graf nie posiada Cyklu Eulera!");
                    return;
                }
            }
            Console.WriteLine();

            for (int i = 0; i < liczbaWierzcholkow; i++)
            {
                Nullable<int> value = cykl[wierzcholekStart,i];
                while (value.HasValue)
                {
                    cykl[wierzcholekStart,i]--;
                    cykl[i,wierzcholekStart]--;
                    Euler(i);
                }
                wypiszCykl[s++] = wierzcholekStart;
                Console.Write(wypiszCykl[s++] + " -> ");
            }
        }

    }


    class Program
    {
        static void Main(string[] args)
        {
            Graf g1 = new Graf();
            g1.zbudujGraf();
            //g1.wyświetlListęSąsiadów();
            //g1.wczytajGraf();
            //g1.usuńKrawędź(1, 3);
            g1.wyświetlListęSąsiadów();
            g1.DFS(1);
            g1.Euler(1);

            Console.ReadKey();
        }
    }
}