/**
	Алгоритъм на Крускал за минимално покриващо дърво (с Union-find структура)
*/

#include <iostream>
#include <algorithm>
using namespace std;

class UFS // Union-Find структура с фиксиран брой елементи
{
	int size;
	int* parent;
	int* rank;

public:
	UFS(int s)
	{
		parent = new int[s];
		rank = new int[s];
		size = s;
		for (int i = 0; i < s; i++){ parent[i] = i; rank[i] = 0; }
	}

	int find(int x)
	{
		if (parent[x] != x) parent[x] = find(parent[x]);
		return parent[x];
	}

	void unite(int x, int y)
	{
		int rx = find(x);
		int ry = find(y);

		if (rx != ry)
		{
			if (rank[rx] > rank[ry]) parent[ry] = rx;
			else if (rank[rx] < rank[ry]) parent[rx] = ry;
			else { parent[ry] = rx; rank[rx]++; }
		}
	}
};

const int n = 8, m = 11;

struct edge
{
	int u, v, w;
	edge() :u(0), v(0), w(0){}
	edge(int u_, int v_, int w_) :u(u_), v(v_), w(w_){}
	edge& operator = (edge& e){ u = e.u; v = e.v; w = e.w; return *this; }
	bool operator < (const edge &e) const { return w < e.w; }
};

edge graph[m] = {
	edge(0, 1, 1), edge(0, 3, 3), edge(0, 4, 5),
	edge(1, 2, 2), edge(1, 5, 2),
	edge(2, 4, 6),
	edge(3, 6, 10),
	edge(4, 6, 7), edge(4, 7, 2),
	edge(5, 7, 5), edge(6, 7, 20) }; // неориентиран граф като списък от ребра

edge MPD_Result[n];
int c;

int MST_Kruskal()
{
	sort(graph, graph + m);

	UFS s(n);
	int sum = 0;
	c = 0;

	for (int i = 0; i < m && c < n - 1; i++)
	{
		edge e = graph[i];
		if (s.find(e.u) != s.find(e.v))
		{
			sum += e.w;
			MPD_Result[c++] = e;
			s.unite(e.u, e.v);
		}
	}

	return sum;
}

int main()
{
	cout << "MPD_Sum = " << MST_Kruskal() << endl;

	return 0;
}