крускал

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

namespace MibOstTreeWithDSU
{
    struct Edge
    {
        public readonly int v1, v2, weight;
        public Edge(int v1, int v2, int weight)
        {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }
        public override string ToString()
        {
            return String.Format("[({0},{1}), w = {2}]", v1, v2, weight);
        }
    }

    class DSU
    {
        private int[] p;
        private int[] cnt;
        public DSU(int size)
        {
            p = new int[size];
            cnt = new int[size];
            for (int i = 0; i < size; ++i)
            {
                p[i] = i;
                cnt[i] = 1;
            }
        }
        public int getID(int vertex)
        {
            if (p[vertex] == vertex) return vertex;
            return p[vertex] = getID(p[vertex]);
        }
        public bool unite(int a, int b)
        {
            a = getID(a);
            b = getID(b);
            if (a == b) return false;
            if (cnt[a] > cnt[b])
            {
                cnt[a] += cnt[b];
                p[b] = a;
            }
            else
            {
                cnt[b] += cnt[a];
                p[a] = b;
            }
            return true;
        }
    }

    class Program
    {
        public static List<int> Kraskall(int n, Edge[] G, out int SumW)
        {
            int m = G.Length;
            int[] ord = new int[m];
            for (int i = 0; i < m; ++i)
                ord[i] = i;
            Array.Sort(ord, (int x, int y) =>
            {
                return G[x].weight.CompareTo(G[y].weight);
            });
            DSU dsu = new DSU(n);

            List<int> ans = new List<int>(n - 1);
            SumW = 0;
            foreach (int id in ord)
            {
                if (dsu.unite(G[id].v1, G[id].v2))
                {
                    ans.Add(id);
                    SumW += G[id].weight;
                }
            }
            return ans;
        }

        static void Main(string[] args)
        {
            int n = 5;
            Random rand = new Random(15);
            Edge[] G = new Edge[n * (n - 1) / 2];
            for (int i = 0, pos = 0; i < n; ++i)
                for (int j = 0; j < i; ++j, ++pos)
                {
                    G[pos] = new Edge(i, j, rand.Next(100));
                }
            Console.WriteLine("============Graph============");
            foreach (Edge e in G)
                Console.WriteLine(e);
            Console.WriteLine("=============================");

            int w;
            List<int> ostTr = Kraskall(n, G, out w);
            Console.WriteLine("Min ost. tree weight = {0}", w);
            foreach(int id in ostTr)
            {
                Console.Write(id + " ");
            }
        }
    }
}