1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using System.Text;
5. using System.Threading.Tasks;
6.  
7. namespace Kruskal
8. {
9.     class Program
10.     {
11.         class Edge
12.         {
13.             public int p1, p2, weight;
14.         }
15.         class Subset
16.         {
17.             public int Parent;
18.             public int Rank;
19.         }
20.         class Graph
21.         {
22.             public Edge[] Edges;
23.             public int EdgeCount;
24.             public int VerCount;
25.  
26.             public Graph CreateGraph(int verCount, int edgeCount)
27.             {
28.                 Graph graf = new Graph();
29.                 graf.VerCount = verCount;
30.                 graf.EdgeCount = edgeCount;
31.                 graf.Edges = new Edge[graf.EdgeCount];
32.  
33.                 return graf;
34.             }
35.  
36.             private int Find(Subset[] subsets, int i)
37.             {
38.                 if (subsets[i].Parent != i)
39.                 {
40.                     subsets[i].Parent = Find(subsets, subsets[i].Parent);
41.                 }
42.                 return subsets[i].Parent;
43.             }
44.  
45.             private void Union(Subset[] subsets, int x, int y)
46.             {
47.                 int xroot = Find(subsets, x);
48.                 int yroot = Find(subsets, y);
49.  
50.                 if (subsets[xroot].Rank < subsets[yroot].Rank)
51.                     subsets[xroot].Parent = yroot;
52.                 else if (subsets[xroot].Rank > subsets[yroot].Rank)
53.                     subsets[yroot].Parent = xroot;
54.                 else
55.                 {
56.                     subsets[yroot].Parent = xroot;
57.                     ++subsets[xroot].Rank;
58.                 }
59.             }
60.             private void Print(Edge[] results, int e)
61.             {
62.                 for (int i = 0; i < e; i++)
63.                 {
64.                     Console.WriteLine("{a} -- {b} == {c}", results[i].p1, results[i].p2, results[i].weight);
65.                 }
66.             }
67.             public void Kruskal(Graph graf)
68.             {
69.                 int verCount = graf.VerCount;
70.                 Edge[] results = new Edge[verCount];
71.                 int i = 0;
72.                 int e = 0;
73.  
74.                 Array.Sort(graf.Edges, delegate (Edge a, Edge b)
75.                  {
76.                      return a.weight.CompareTo(b.weight);
77.                  });
78.                 Subset[] subsets = new Subset[verCount];
79.  
80.                 for (int v = 0; v < verCount; v++)
81.                 {
82.                     subsets[v].Parent = v;
83.                     subsets[v].Rank = 0;
84.                 }
85.                 while (e < verCount - 1)
86.                 {
87.                     Edge nextEdge = graf.Edges[i++];
88.                     int x = Find(subsets, nextEdge.p1);
89.                     int y = Find(subsets, nextEdge.p2);
90.  
91.                     if (x != y)
92.                     {
93.                         results[e++] = nextEdge;
94.                         Union(subsets, x, y);
95.                     }
96.                 }
97.                 Print(results, e);
98.             }
99.         }
100.         static void Main(string[] args)
101.         {
102.             Graph graph=new Graph();
103.             graph.CreateGraph(4, 5);
104.             // Edge 0-1
105.             graph.Edges[0].p1 = 0;
106.             graph.Edges[0].p2 = 1;
107.             graph.Edges[0].weight = 10;
108.  
109.             // Edge 0-2
110.             graph.Edges[1].p1 = 0;
111.             graph.Edges[1].p2 = 2;
112.             graph.Edges[1].weight = 6;
113.  
114.             // Edge 0-3
115.             graph.Edges[2].p1 = 0;
116.             graph.Edges[2].p2 = 3;
117.             graph.Edges[2].weight = 5;
118.  
119.             // Edge 1-3
120.             graph.Edges[3].p1 = 1;
121.             graph.Edges[3].p2 = 3;
122.             graph.Edges[3].weight = 15;
123.  
124.             // Edge 2-3
125.             graph.Edges[4].p1 = 2;
126.             graph.Edges[4].p2 = 3;
127.             graph.Edges[4].weight = 4;
128.  
129.             graph.Kruskal(graph);
130.         }
131.     }
132. }
133.