G6 - MST-Kruskal

template< class type >
class MST_Kruskal {
	const int n, m;
	class Union_Find {
		int ar[maxn+1] {};
		int dsu(const int x) {
			if (x != ar[x]) ar[x] = dsu(ar[x]);
			return ar[x];
		}
	public:
		explicit Union_Find(const int n) { for (int i = 1; i <= n; i++) ar[i] = i; }
		bool query(const int x, const int y) { return dsu(x) == dsu(y); }
		void merge(const int x, const int y) { ar[dsu(y)] = dsu(x); }
	} uf;
public:
	struct node {
		int e, u, len;
		friend bool operator<(const node &a, const node &b) { return a.len < b.len; }
	} ar[maxm];
	explicit MST_Kruskal(const int n, const int m): n(n), m(m), uf(n) {}
	pair<bool, type> solve() {
		sort(ar, ar+m);
		type ret = 0, cnt = 1;
		for (int i = 0; i < m; i++) if (!uf.query(ar[i].e, ar[i].u)) {
				ret += ar[i].len;
				uf.merge(ar[i].e, ar[i].u);
				++cnt;
			}
		return {cnt == n, ret};
	}
};