using System;
using System.Collections.Generic;
using System.Windows.Forms;

namespace Cwiczenia13_12_23
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            Wezel4 wezel1 = new Wezel4(1);
            Wezel4 wezel2 = new Wezel4(2);
            Wezel4 wezel3 = new Wezel4(3);

            Krawedz krawedz1 = new Krawedz(wezel1, wezel2, 10);
            Krawedz krawedz2 = new Krawedz(wezel2, wezel3, 20);

            Graf graf = new Graf(krawedz1);
            graf.addANewPoint(wezel3);

            Graf minimumSpanningTree = graf.KruskalAlgorithm();

            // Wyświetlenie wynikowego minimalnego drzewa rozpinającego
            foreach (Krawedz krawedz in minimumSpanningTree.krawedzie)
            {
                Console.WriteLine($"Start: {krawedz.poczatek.wartosc}, Koniec: {krawedz.koniec.wartosc}, Waga: {krawedz.waga}");
            }
        }
    }

    class Krawedz
    {
        public int waga;
        public Wezel4 poczatek;
        public Wezel4 koniec;

        public Krawedz(Wezel4 firstPoint, Wezel4 secondPoint, int waga)
        {
            this.poczatek = firstPoint;
            this.koniec = secondPoint;
            this.waga = waga;
        }
    }

    class Wezel4
    {
        public int wartosc;

        public Wezel4(int wartosc)
        {
            this.wartosc = wartosc;
        }
    }

    class Graf
    {
        public List<Krawedz> krawedzie;
        public List<Wezel4> wierzcholki;

        public Graf(Krawedz firstLink)
        {
            wierzcholki = new List<Wezel4>();
            krawedzie = new List<Krawedz>();
            this.wierzcholki.Add(firstLink.poczatek);
            this.wierzcholki.Add(firstLink.koniec);
            this.krawedzie.Add(firstLink);
        }

        /// <summary>
        /// The nuclear option, create a new graph straight away with the provided lists
        /// </summary>
        /// <param name="krawedzie"></param>
        /// <param name="wierzcholki"></param>
        public Graf(List<Krawedz> krawedzie, List<Wezel4> wierzcholki)
        {
            this.wierzcholki = new List<Wezel4>();
            this.krawedzie = new List<Krawedz>();
            this.krawedzie = krawedzie;
            this.wierzcholki = wierzcholki;
        }

        public int newGraphsNeeded(Krawedz krawedz)
        {
            int newGraphCount = 0;
            if (!wierzcholki.Contains(krawedz.poczatek))
                newGraphCount++;
            if (!wierzcholki.Contains(krawedz.koniec))
                newGraphCount++;

            return newGraphCount;
        }

        public Graf KruskalAlgorithm()
        {
            var krawedzie = this.krawedzie.OrderBy(k => k.waga);
            List<Graf> listaGrafow = new List<Graf>();

            foreach (var krawedz in krawedzie)
            {
                if (listaGrafow.Count == 0)
                {
                    listaGrafow.Add(new Graf(krawedz));
                    continue;
                }

                Graf graph1 = null;  // graf, do którego należy początek krawędzi
                Graf graph2 = null;  // graf, do którego należy koniec krawędzi

                // Sprawdzanie, do których grafów należą węzły początkowe i końcowe krawędzi
                foreach (var graph in listaGrafow)
                {
                    if (graph.wierzcholki.Contains(krawedz.poczatek))
                    {
                        if (graph1 == null)
                            graph1 = graph;
                        else
                            graph2 = graph;
                    }

                    if (graph.wierzcholki.Contains(krawedz.koniec))
                    {
                        if (graph1 == null)
                            graph1 = graph;
                        else
                            graph2 = graph;
                    }
                }

                if (graph1 != graph2)  // jeżeli wierzchołki należą do różnych grafów
                {
                    // Dodawanie krawędzi do grafu
                    graph1.krawedzie.Add(krawedz);

                    // Łączenie grafów
                    graph1.mergeGraph(graph2);
                    listaGrafow.Remove(graph2);
                }
            }

            // Zwracanie grafu z minimalnym drzewem rozpinającym
            return listaGrafow[0];
        }

        public void mergeGraph(Graf otherGraph)
        {
            foreach (Krawedz krawedz in otherGraph.krawedzie)
            {
                this.krawedzie.Add(krawedz);
            }

            foreach (Wezel4 wierzcholek in otherGraph.wierzcholki)
            {
                this.wierzcholki.Add(wierzcholek);
            }
        }

        public void addANewPoint(Wezel4 pointToAdd)
        {
            if (!wierzcholki.Contains(pointToAdd))
            {
                wierzcholki.Add(pointToAdd);
            }
        }
    }
}