并查集[讲义]

《并查集[讲义]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并查集初步及应用引例：犯罪团伙1、最小生成树2、细胞个数3、房间问题(noi94)4、代码等式5、银河英雄传说(noi2002)并查集的概念及运算内容：引例：【犯罪团伙】警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。输入：第一行：n（<=10000,罪犯数量），第二行：m（<=100000，关系数量）以下若干

2、行：每行两个数：I和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。输出：一个整数，犯罪团伙的数量。输入：118124534135671051089输出：3测试数据说明：1s共10个测试数据：（1）5个数据：n<=1000,m<=5000;（2）5个数据：10000>=n>=9000,100000>=m>=90000;建立无向图的模型。☻如果x和y认识，结点x和y建立一条无向边。☻求无向图的连通分量（dfs;bfs）☻时间和空间！邻接矩阵：空间太大，超时。邻接表：空间满足，时间查过1s最容易想到的算法：抽象的算法：◆开始把n个人看成

3、n个独立集合。◆每读入两个有联系的人i和j，查找i和j所在的集合p和q，如果p和q是同一个集合，不作处理；如果p和q属于不同的集合，则合并p和q为一个集合。◆最后统计集合的个数即可得到问题的解。需要将n个不同的元素划分成一组不相交的集合。开始时，每个元素自己成一个单元素集合，然后按照一定的顺序或问题给定的条件和要求将属于同一组元素（有特定关系）所在的集合合并，最后统计集合的个数往往就是问题的解。在这个过程中要反复的用到查询某个元素属于哪个集合的运算；两个不同集合合并的运算。适合描述这类问题的抽象数据结构类型称为并查集（合并与查找）。一类

4、问题模型：◆并查集是一种树型的数据结构，用于处理一些不相交集合S={S1,S2,…,Sn},每个集合Si都有一个特殊元素root[Si],称为集合的代表元.◆并查集支持三种操作：Init（X）:集合初始化：把元素xi加到集合Si中。每个集合Si只有一个独立的元素xi,并且元素xi就是集合Si的代表元素。Find(x):查找：查找xi所在集合Si的代表root[Si]。优化：路径压缩。Union(x,y):合并：把x和y所在的两个不同集合合并。并查集的一个重要的应用是确定给定集合上的等价关系的个数。等价关系是一个具有自反、对称和传递三个性

5、质的关系。等号“=”在实数集合R上是一个等价关系。对于实数中的任意x、y、z。一定满足下列关系：1）、x=x（自反性）2）、如果x=y，则y=x（对称性）3）、如果x=y，y=z，则x=z（传递性）【犯罪团伙】问题：“同一团伙“抽象成无向图的”连通””连通”可以看成n个人的集合上的一个等价关系。对于图中的任意3个顶点：A,B,C。有：1）、A连通A.（自反性）2）、如果A连通B，则B连通A.（对称性）3）、如果A连通B，B连通C，则A连通C.（传递性）一个连通分量就是一个等价关系（连通），等价关系的个数就是连通分量的个数。一个等价关系对

6、应一个集合。一个集团对应一个集合。并查集的树型结构实现采用树型结构实现并查集的基本思想是：◆每个子集合用一棵树来表示。树中的每个结点用于存放集合中的一个元素。◆树中的每个结点x设置一个指向父亲的指针。father[x]◆用根结点的元素代表该树所表示的集合。►Init（X）:集合初始化：father[xi]=0(或者xi);每个结点都是一颗独立的树，是该树的代表元素。三种操作：►Find(x):查找：查找x所在集合Si的代表root[Si]。即：查找x所在树的树根结点（代表元素）。顺着x往上找，直到找到根节点，也就确定了x所在的集合。

7、►Union(x,y):合并x和y所在的不同集合。p=find(x)；q=find(y);ifp<>qthenfather[p]=q或father[q]=p2131145610798输入：1181245341356710510891121634510798初始化:合并:树根（集合代表元素）：Father[1]=0;father[8]=0;father[11]=0孩子结点：father[2]=1;father[4]=3;father[5]=4;father[9]=8查找：find(5)=1find(7)=1find(9)=8

8、find(11)=11find(1)=1find(8)=8合并：union（x，y）union（5，9）p=find(5)=1;q=find(9)=8;father[q]=p;或father[p]=q