克鲁斯卡尔求最小生成树

思想：首先将 $n$ 个点看做 $n$ 个独⽴的集合，将所有边快排(从小到大)。然后，按排好的顺序枚举每⼀条边， 判断这条边连接的两个点是否属于⼀个集合。若是，则将这条边加⼊最小生成树，并将两个点所在的集合合并为⼀个集合。若否，则跳过。直到找到 $n-1$ 条边为止。

#include<iostream>
#include<algorithm>
using namespace std;
struct point {
	int x;
	int y;
	int v;
};
point a[10000];

int cmp(const point & a, const point & b) {
	if (___(1)___ ) return 1;
	else return 0;
}

int fat[101];
int father(int x) {
	if (fat[x] != x) return fat[x] = ___(2)___ ;
	else return fat[x];
}

void unionn(int x, int y) {
	int fa = father(x);
	int fb = father(y);
	if (fa != fb) fat[fa] = fb;
}

int main() {
	int i, j, n, m, k = 0, ans = 0, cnt = 0;
	cin >> n;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++) {
			cin >> m;
			if (m != 0) {
				k++;
				a[k].x = i;
				a[k].y = j;
				a[k].v = m;
			}
		}
	sort(a + 1, a + 1 + k; ___(3)___ );

	for (i = 1; i <= n; i++) {
		fat[i] = i;
	}

	for (i = 1; i <= k; i++) {
		if (father(a[i].x) != ___(4)___ ) {
			ans += a[i].v;
			unionn(a[i].x, a[i].y);
			cnt++;
		}
		if (___(5)___) break;
	}
	cout << ans;
	return 0;
}