擒贼先擒王——并查集

今天复习了一下堆的两种排序方法，又学习了一下并查集。

下附上问题描述和代码

#include<iostream>
using namespace std;
int f[1001] = { 0 }, n, m, sum = 0;

//初始化函数
void init() {
	int i;
	for (i = 1; i <= n; i++)
		f[i] = i;
	return;
}

//找爹且擒贼先擒王
int getf(int v) {
	if (f[v] == v)
		return v;
	else {
		//路径压缩，每次函数返回的时候，顺带把路上遇到的人的"BOSS"改为最后找到的祖宗编号；
		//提高找祖先的速度。
		f[v] = getf(f[v]);
		return f[v];
	}
}

//合并两子集合的函数
void merge(int v, int u) {
	int t1, t2;
	t1 = getf(v);//t1,t2分别为v和u的最大BOSS
	t2 = getf(u);
	if (t1 != t2)
		f[t2] = t1;//靠左原则
}

int main() {
	int i, x, y;
	scanf("%d %d",&n, &m);//n是有多少个犯罪个体，m是由多少条描述
	init();//初始化
	for (i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		merge(x, y);
	}

	//扫描有多少个独立的犯罪团伙
	for (i = 1; i <= n; i++)
		if (f[i] == i)
			sum++;

	printf("%d\n", sum);
	system("pause");
}

最终返回的是有多少个独立团伙。

运行结果：

最后结果是3.

附上今日份的山大月饼，馋你们。