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

namespace Kruskal
{
    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.Kruskal();
            for (int i = 0; i < graf.kruskal_kr.Length; i++)
                Console.WriteLine(graf.kruskal_kr[i]);
            Console.Read();
        }
    }
    class Node
    {
        public string wartosc;
        public Node(string wartosc)
        {
            this.wartosc = wartosc;
        }
        public override string ToString()
        {
            return this.wartosc.ToString();
        }
    }
    class Krawedz
    {
        public Node start;
        public Node koniec;
        public int waga;
        public Krawedz(Node s, Node k, int w = 1)
        {
            this.start = s;
            this.koniec = k;
            this.waga = w;
        }
        public override string ToString()
        {
            return $"{this.start} - {this.koniec} ({this.waga})";

        }
        public Node ZnajdzDrugi(Node n)
        {
            return this.start == n ? this.koniec : this.start;
        }
    }
    class Graph
    {
        public List<Node> wierzcholki = new List<Node>();
        public List<Krawedz> krawedzie = new List<Krawedz>();
        public Krawedz[] kruskal_kr;
        List<Node> odwiedzone = new List<Node>();
        public List<Krawedz> ZnajdzKrawedzie(Node n)
        {
            List<Krawedz> wynik = new List<Krawedz>();
            for (int i = 0; i < krawedzie.Count; i++)
            {
                var k = this.krawedzie[i];
                if (k.start == n || k.koniec == n)
                {
                    wynik.Add(k);
                }
            }
            return wynik;
        }

        public void Kruskal()
        {
            kruskal_kr = new Krawedz[wierzcholki.Count - 1];
            var posortowane_kraw = krawedzie.OrderBy(x => x.waga);
            Dictionary<Node, Krawedz> s_wierzcholkow = new Dictionary<Node, Krawedz>();
            foreach(var x in wierzcholki)
            {
                s_wierzcholkow[x] = null;
            }
            int ilosc_wierz = 0;
            foreach(var x in posortowane_kraw)
            {
                if (ilosc_wierz == this.wierzcholki.Count) break;
                if (s_wierzcholkow[x.start] == null || s_wierzcholkow[x.start] != s_wierzcholkow[x.koniec])
                {
                    kruskal_kr[ilosc_wierz] = x;
                    ilosc_wierz++;
                    if (s_wierzcholkow[x.start] != null || s_wierzcholkow[x.koniec] != null)
                    {
                        var set1 = s_wierzcholkow[x.start];
                        var set2 = s_wierzcholkow[x.koniec];

                        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] = x;
                    }
                    s_wierzcholkow[x.start] = x;
                    s_wierzcholkow[x.koniec] = x;
                }
            }
        }
    }
}