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

namespace Kruskal
{
    class Program
    {
        class Edge
        {
            public int p1, p2, weight;
        }
        class Subset
        {
            public int Parent;
            public int Rank;
        }
        class Graph
        {
            public Edge[] Edges;
            public int EdgeCount;
            public int VerCount;

            public Graph CreateGraph(int verCount, int edgeCount)
            {
                Graph graf = new Graph();
                graf.VerCount = verCount;
                graf.EdgeCount = edgeCount;
                graf.Edges = new Edge[graf.EdgeCount];

                return graf;
            }

            private int Find(Subset[] subsets, int i)
            {
                if (subsets[i].Parent != i)
                {
                    subsets[i].Parent = Find(subsets, subsets[i].Parent);
                }
                return subsets[i].Parent;
            }

            private void Union(Subset[] subsets, int x, int y)
            {
                int xroot = Find(subsets, x);
                int yroot = Find(subsets, y);

                if (subsets[xroot].Rank < subsets[yroot].Rank)
                    subsets[xroot].Parent = yroot;
                else if (subsets[xroot].Rank > subsets[yroot].Rank)
                    subsets[yroot].Parent = xroot;
                else
                {
                    subsets[yroot].Parent = xroot;
                    ++subsets[xroot].Rank;
                }
            }
            private void Print(Edge[] results, int e)
            {
                for (int i = 0; i < e; i++)
                {
                    Console.WriteLine("{a} -- {b} == {c}", results[i].p1, results[i].p2, results[i].weight);
                }
            }
            public void Kruskal(Graph graf)
            {
                int verCount = graf.VerCount;
                Edge[] results = new Edge[verCount];
                int i = 0;
                int e = 0;

                Array.Sort(graf.Edges, delegate (Edge a, Edge b)
                 {
                     return a.weight.CompareTo(b.weight);
                 });
                Subset[] subsets = new Subset[verCount];

                for (int v = 0; v < verCount; v++)
                {
                    subsets[v].Parent = v;
                    subsets[v].Rank = 0;
                }
                while (e < verCount - 1)
                {
                    Edge nextEdge = graf.Edges[i++];
                    int x = Find(subsets, nextEdge.p1);
                    int y = Find(subsets, nextEdge.p2);

                    if (x != y)
                    {
                        results[e++] = nextEdge;
                        Union(subsets, x, y);
                    }
                }
                Print(results, e);
            }
        }
        static void Main(string[] args)
        {
            Graph graph=new Graph();
            graph.CreateGraph(4, 5);
            // Edge 0-1
            graph.Edges[0].p1 = 0;
            graph.Edges[0].p2 = 1;
            graph.Edges[0].weight = 10;

            // Edge 0-2
            graph.Edges[1].p1 = 0;
            graph.Edges[1].p2 = 2;
            graph.Edges[1].weight = 6;

            // Edge 0-3
            graph.Edges[2].p1 = 0;
            graph.Edges[2].p2 = 3;
            graph.Edges[2].weight = 5;

            // Edge 1-3
            graph.Edges[3].p1 = 1;
            graph.Edges[3].p2 = 3;
            graph.Edges[3].weight = 15;

            // Edge 2-3
            graph.Edges[4].p1 = 2;
            graph.Edges[4].p2 = 3;
            graph.Edges[4].weight = 4;

            graph.Kruskal(graph);
        }
    }
}