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 + " ");
}
}
}
}