并查集

一、什么是并查集

• 概念：并查集由一个整型数组pre[ ]和两个函数find( )、join( )构成。数组pre[ ]记录了每个点的前导点是什么，函数find(x)用于查找，函数join(x,y)用于合并。
• 作用：并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2……）
• 应用场景：当问题满足对一个给定集合中的元素根据不同特点分类成子集合再做处理的时候，我们可以使用并查集来方便我们分类，确定每个子集合中个元素的关联性。

我们拿一个题目来辅助说明：
  w星球的一个种植园，被分成 m * n
个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
  这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
  如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
  
输入格式
  第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
  接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
  接下来k行，第2+k行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
  
样例输入
5 4    //m,m的值
16    //格子总数
2 3    //以下都是两辆连根的植物
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

  问题分析：16格植物相当于一个大集合，然后根部连在一起的相当于一个子集，我们需要求出在给定条件下有多少个子集即可，接下来看并查集如何一步一步实现。

二、Init()函数

  我们每次使用并查集的时候，都要对给定集合做一个初始化，方便我们后面使用这个集合。初始化的目的很简单，就是将该集合的每个元素的根节点都设置成自己本身。

const int MAX = 100010;		//设置集合做大size
int pre[MAX];				//记录每个元素对应的上一个节点的数组

void Init(vector<int> vi) {
	for(int i = 0; i < vi.sie(); ++i) {
		pre[i] = vi[i];
	}
}

三、find()函数

  我们先来看一下find()函数的原理和作用。find函数用来找出给定元素的根节点，我们可以从该元素的上一个节点入手，然后递归找下去，直到有一个元素的上一个节点是他自己，那么说明，这个节点就是给定元素的根节点（使劲理解这里，没理解就不要往下看）。

int Find(int x) {
	if(pre[x] == x) {
		return x;
	} else {
		return pre[x] = Find(pre[x]);
	}
}

四、Join()函数

  找根节点的函数准备好了，我们还缺一个给元素两辆确定关系的函数，那就是join()函数，该函数的意义就是根据问题要求来给不同的若干个元素建立联系。如何建立呢，看代码就行了。

int Join(int x, int y) {
	int xRoot = Find(x);
	int yRoot = Find(y);
	if(xRoot != yRoot) {
		pre[x] = yRoot;
	}
}

  分别用find函数找出x,y的根节点，如果发现他们的根节点不同，那么就将其中一个人的前置节点设置为另一个人的根节点，这样的话，他们就相当于有了相同的根节点，就像题目里说的那样，他们属于连根植物了，专业一点就是他们现在处于一个连通图里，属于集合中的一个子集内。

五、题解全代码

#include <iostream>

using namespace std;

const int MAX = 10000;
int m, n;
int pre[MAX] = {0};

void Init(int x) {
	for(int i = 1; i <= x; ++i) {
		pre[i] = i;
	}
}

int FindPre(int x) {
	if(pre[x] == x) {
		return x;
	} else {
		return pre[x] = FindPre(pre[x]);	//路径压缩
	}
}

void Union(int x, int y) {
	int xRoot = FindPre(x);
	int yRoot = FindPre(y);

	if(xRoot != yRoot) {
		pre[xRoot] = yRoot;
	}
}

int main() {
	int x, y, line;
	cout << "input m/n/line: " << endl;
	cin >> m >> n >> line;
	Init(m*n);
	for(int i = 0; i < line; ++i) {
		cout << "input union x/y: " << endl;
		cin >> x >> y;
		Union(x, y);
	}
	
	int result = 0, root[MAX] = {0};
	for(int i = 0; i < m*n; ++i) {
		root[FindPre(i)] = 1;
	}
	for(int i = 0; i < m*n; ++i) {
		if(root[i] == 1) {
			result++;
		}
	}
	cout << "result = " << result << endl;
	
	return 0;
}

六、总结

  并查集的作用就是求联通分支数，确定一个大集合中各元素之间的关联关系。建立一个并查集的固定步骤就是先对集合初始化，将每个元素的前置节点都设为自己。然后再设计一个根节点查找函数，该函数也很简单，就是递归遍历自己的前置节点，直到有一个节点的的前置节点是他自己，说明他没有前置节点，那么他一定是一个根节点。最后要设计一个给各个元素建立关系的函数，该函数通过对比输入元素的根节点来确认他们是否属于同一个集合，如果有相同的根节点，那么就是同一条船上的人，如果没有，那么根据问题要求将他们建立关系，就是把其中一个人的根节点设置为另一个人的根节点，那么他们以后就是一条船上的人了。
  以上，建立好并查集之后，我们就可以按找具体的问题要求，来获取我们想要的结果，比如例题，我们就可以通过遍历集合的每个元素，来统计一共有几个不同的根节点就算出了有几个不同的子集，也就是有几根连根植物。