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

namespace Kolokwium
{
    class Program
    {
        static void Main(string[] args)
        {
            Graph graf = new Graph();
            Node Wezel1 = new Node("a");
            Node Wezel2 = new Node("b");
            Node Wezel3 = new Node("c");
            Node Wezel4 = new Node("d");
            Node Wezel5 = new Node("e");
            Node Wezel6 = new Node("f");
            Node Wezel7 = new Node("g");
            Krawedz edge1 = new Krawedz(Wezel1, Wezel2, 7);
            Krawedz edge2 = new Krawedz(Wezel1, Wezel4, 5);
            Krawedz edge3 = new Krawedz(Wezel2, Wezel3, 8);
            Krawedz edge4 = new Krawedz(Wezel2, Wezel5, 7);
            Krawedz edge5 = new Krawedz(Wezel2, Wezel4, 9);
            Krawedz edge6 = new Krawedz(Wezel4, Wezel5, 15);
            Krawedz edge7 = new Krawedz(Wezel4, Wezel6, 6);
            Krawedz edge8 = new Krawedz(Wezel6, Wezel5, 8);
            Krawedz edge9 = new Krawedz(Wezel6, Wezel7, 11);
            Krawedz edge10 = new Krawedz(Wezel3, Wezel5, 5);
            Krawedz edge11 = new Krawedz(Wezel5, Wezel7, 9);
            graf.wierzcholki.Add(Wezel1);
            graf.wierzcholki.Add(Wezel2);
            graf.wierzcholki.Add(Wezel3);
            graf.wierzcholki.Add(Wezel4);
            graf.wierzcholki.Add(Wezel5);
            graf.wierzcholki.Add(Wezel6);
            graf.wierzcholki.Add(Wezel7);
            graf.krawedzie.Add(edge1);
            graf.krawedzie.Add(edge2);
            graf.krawedzie.Add(edge3);
            graf.krawedzie.Add(edge4);
            graf.krawedzie.Add(edge5);
            graf.krawedzie.Add(edge6);
            graf.krawedzie.Add(edge7);
            graf.krawedzie.Add(edge8);
            graf.krawedzie.Add(edge9);
            graf.krawedzie.Add(edge10);
            graf.krawedzie.Add(edge11);
            //graf.DFS(Wezel1);
            //var podgraf = graf.Prima(Wezel1);
            //foreach(var k in podgraf.wierzcholki)
            //{
            //    Console.WriteLine(k);
            //}
            //graf.Disktryj(Wezel1);
            graf.Kruskal(Wezel1);
            Console.Read();
        }
    }
    public class Node
    {
        public string wartosc;
        public Node(string wartosc)
        {
            this.wartosc = wartosc;
        }
        public override string ToString()
        {
            return this.wartosc.ToString();
        }
    }
    public class Krawedz
    {
        public Node start;
        public Node koniec;
        public int waga;
        public Krawedz(Node s, Node k, int w)
        {
            this.start = s;
            this.koniec = k;
            this.waga = w;
        }
        public Node ZnajdzDrugi(Node n)
        {
            return this.start == n ? this.koniec : this.start;
        }
        public override string ToString()
        {
            return $"{this.start} - {this.koniec}({this.waga})";
        }
    }
    public class Para
    {
        public Node prev;
        public int dlugosc;
        public Para(Node n, int d)
        {
            this.prev = n;
            this.dlugosc = d;
        }
    }
    class Graph
    {
        public List<Krawedz> krawedzie = new List<Krawedz>();
        public List<Node> wierzcholki = new List<Node>();
        public List<Node> odwiedzone = new List<Node>();
        public Dictionary<Node, Para> tabelka = new Dictionary<Node, Para>();
        Krawedz[] kr_kruskal;
        public List<Krawedz> ZnajdzKrawedzie(Node n)
        {
            List<Krawedz> wynik = new List<Krawedz>();
            foreach(var x in krawedzie)
            {
                if(x.start == n || x.koniec == n)
                {
                    wynik.Add(x);
                }
            }
            return wynik;
        }
        public void DFS(Node n)
        {
            odwiedzone.Add(n);
            Console.WriteLine("Odwiedzono wierzcholek: " + n.wartosc);
            var l_krawedz = ZnajdzKrawedzie(n);
            foreach(var x in l_krawedz)
            {
                if (!odwiedzone.Contains(x.ZnajdzDrugi(n)))
                {
                    DFS(x.ZnajdzDrugi(n));
                }
            }
        }
        public void BFS(Node n)
        {
            Queue<Node> kolejka = new Queue<Node>();
            kolejka.Enqueue(n);
            odwiedzone.Add(n);
            while (kolejka.Count > 0)
            {
                n = kolejka.Dequeue();
                Console.WriteLine("Odwiedzono wierzcholek: " + n.wartosc);
                var l_krawedzi = ZnajdzKrawedzie(n);
                foreach(var x in l_krawedzi)
                {
                    if (!odwiedzone.Contains(x.ZnajdzDrugi(n))){
                        kolejka.Enqueue(x.ZnajdzDrugi(n));
                        odwiedzone.Add(x.ZnajdzDrugi(n));
                    }
                }
            }
        }
        public Graph Prima(Node n)
        {
            Graph podgraf = new Graph();
            podgraf.wierzcholki.Add(n);
            List<Krawedz> l_krawedzi = new List<Krawedz>();
            var kraw = ZnajdzKrawedzie(n);
            l_krawedzi.AddRange(kraw);
            l_krawedzi = l_krawedzi.OrderBy(x => x.waga).ToList();
            while(l_krawedzi.Count>0)
            {
                odwiedzone.Add(n);
                var kra = ZnajdzKrawedzie(n);
                l_krawedzi.AddRange(kra);
                l_krawedzi = l_krawedzi.OrderBy(x => x.waga).ToList();
                foreach(var k in l_krawedzi.ToList())
                {
                    if(odwiedzone.Contains(k.koniec) && odwiedzone.Contains(k.start))
                    {
                        l_krawedzi.Remove(k);
                    }
                    if (!odwiedzone.Contains(k.koniec) && odwiedzone.Contains(k.start))
                    {
                        n = k.koniec;
                        podgraf.wierzcholki.Add(n);
                        podgraf.krawedzie.Add(k);
                        l_krawedzi.Remove(k);
                        break;
                    }
                    if (odwiedzone.Contains(k.koniec) && !odwiedzone.Contains(k.start))
                    {
                        n = k.start;
                        podgraf.wierzcholki.Add(n);
                        podgraf.krawedzie.Add(k);
                        l_krawedzi.Remove(k);
                        break;
                    }

                }

            }
            return podgraf;

        }
        public void Disktryj(Node n)
        {
            tabelka.Add(n, new Para(null, 0));
            while (true)
            {
                var element = tabelka.OrderBy(x => x.Value.dlugosc).FirstOrDefault(x => !this.odwiedzone.Contains(x.Key));
                if (element.Key == null) break;
                else
                {
                    odwiedzone.Add(element.Key);
                    var l_krawedzi = ZnajdzKrawedzie(element.Key);
                    foreach(var k in l_krawedzi)
                    {
                        var drugi = k.ZnajdzDrugi(element.Key);
                        if (tabelka.ContainsKey(drugi))
                        {
                            var nowa_dlugosc = element.Value.dlugosc + k.waga;
                            if (tabelka[drugi].dlugosc > nowa_dlugosc)
                            {
                                tabelka[drugi].prev = element.Key;
                                tabelka[drugi].dlugosc = nowa_dlugosc;
                            }
                        }
                        else
                        {
                            tabelka.Add(drugi, new Para(element.Key, element.Value.dlugosc + k.waga));
                        }
                    }
                }
            }
            foreach(var x in tabelka)
            {
                Console.WriteLine(x.Key + "->"+x.Value.prev + "=" + x.Value.dlugosc);
            }
        }
        public void Kruskal(Node n)
        {
            kr_kruskal = new Krawedz[this.wierzcholki.Count - 1];
            var posortowane = krawedzie.OrderBy(x => x.waga);
            Dictionary<Node, Krawedz> s_wierzcholkow = new Dictionary<Node, Krawedz>();
            foreach(var x in wierzcholki)
            {
                s_wierzcholkow[x] = null;
            }
            int licznik = 0;
            foreach(var k in posortowane)
            {
                if (licznik == this.wierzcholki.Count) break;
                if(s_wierzcholkow[k.start] == null || s_wierzcholkow[k.start] != s_wierzcholkow[k.koniec])
                {
                    kr_kruskal[licznik] = k;
                    licznik++;
                    if(s_wierzcholkow[k.koniec] !=null || s_wierzcholkow[k.start] != null)
                    {
                        var set1 = s_wierzcholkow[k.koniec];
                        var set2 = s_wierzcholkow[k.start];
                        for(int i = 0; i<wierzcholki.Count; i++)
                        {
                            if(s_wierzcholkow.ElementAt(i).Value !=null && (s_wierzcholkow.ElementAt(i).Value == set1 || s_wierzcholkow.ElementAt(i).Value== set2))
                            {
                                s_wierzcholkow[s_wierzcholkow.ElementAt(i).Key] = k;
                            }
                        }
                    }
                    s_wierzcholkow[k.koniec] = k;
                    s_wierzcholkow[k.start] = k;
                }
            }
            for(int i =0; i<kr_kruskal.Length; i++)
            {
                Console.WriteLine(kr_kruskal[i]);
            }
        }

    }
}