并查集模板

缘起

市里面最近有很多犯罪分子, 警方想弄清楚他们之间的从属关系——说白了谁是谁的老大. 但是警方从线人那里只得到了诸如A是B的老大这种零散消息. 警方希望能尽快弄清楚从属关系. 于是并查集诞生了

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

#define LOCAL
using namespace std;
const int MAX_NUM = 1000; // 最多1000个点
int f[MAX_NUM],n; // 并查集数组，实际点的个数

void init() {for (int i = 1; i<=n; i++)f[i] = i;} // 伊始每个元素的根节点就是自己， f[i] = j 表示i 所在的树的根节点是j

// 找v的根节点
int getf(int v) { return f[v]==v?v:f[v]=getf(f[v]);}// 注意这句代码将使得一路寻根上去的值都变成根节点的值

void merge(int u,int v){ f[getf(v)] = getf(u);} // 合并

void last(){ for (int i = 1; i<=n; i++) f[i] = getf(i);} // 最后将每个树上的节点的f值改成父节点的索引

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	puts("输入点的个数");
	scanf("%d", &n);
	init();
	int x, y;
	while(~scanf("%d%d", &x,&y)) merge(x,y);
	int sum = 0; // 总共的树的个数
	for (int i = 1; i<=n;i++)if (i==f[i]) sum++;
	last(); // 就只需要知道到底有几棵树而言, 这是不需要调用的
	cout<< sum<<endl;
	return 0;
}
/*
测试数据
10
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
*/

并查集是一款高效，简短的模板, 核心函数只有

getf和merge. 而且每个只有一行代码. 是一个非常好用的板子.