并查集[讲义]VIP免费

并查集初步及应用第一页，共七十七页。引例：犯罪团伙1、最小生成树2、细胞个数3、房间问题(noi94)4、代码等式5、银河英雄传说(noi2002)并查集的概念及运算内容：第二页，共七十七页。引例：【犯罪团伙】警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。输入：第一行：n（<=10000,罪犯数量），第二行：m（<=100000，关系数量）以下若干行：每行两个数：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个人看成n个独立集合。◆每读入两个有联系的人i和j，查找i和j所在的集合p和q，如果p和q是同一个集合，不作处理；如果p和q属于不同的集合，则合并p和q为一个集合。◆最后统计集合的个数即可得到问题的解。第五页，共七十七页。需要将n个不同的元素划分成一组不相交的集合。开始时，每个元素自己成一个单元素集合，然后按照一定的顺序或问题给定的条件和要求将属于同一组元素（有特定关系）所在的集合合并，最后统计集合的个数往往就是问题的解。在这个过程中要反复的用到查询某个元素属于哪个集合的运算；两个不同集合合并的运算。适合描述这类问题的抽象数据结构类型称为并查集（合并与查找）。一类问题模型：第六页，共七十七页。◆并查集是一种树型的数据结构，用于处理一些不相交集合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所在的两个不同集合合并。第七页，共七十七页。并查集的一个重要的应用是确定给定集合上的等价关系的个数。等价关系是一个具有自反、对称和传递三个性质的关系。等号“=”在实数集合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.（传递性）一个连通分量就是一个等价关系（连通），等价关系的个数就是连通分量的个数。一个等价关系对应一个集合。一个集团对应一个集合。第九页，共七十七页。并查集的树型结构实现采用树型结构实现并查集的基本思想是：◆每个子集合用一棵树来表示。树中的每个结点用于存放集合中的一个元素。◆树中的每个结点x设置一个指向父亲的指针。father[x]◆用根结点的元素代表该树所表示的集合。第十页，共七十七页。►Init（X）:集合初始化：father[xi]=0(或者xi);每个结点都是一颗独立的树，是该树的代表元素。三种操作：►Find(x):查找：查找x所在集合Si的代表root[Si]。即：查找x所在树的树根结点（代表元素）。顺着x往上找，直到找到根节点，也就确定了x所在的集合。►Union(x,y):合并x和y所在的不同集合。p=find(x)；q=find(y);ifp<>qthenfather[p]=q或father[q]=p第十一页，共七十七页。2131145610798输入：1181245341356710510891121634510798初始化:合并:第十二页，共七十七页。树根（集合代表元素...