在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内竞赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往超过了空间的限制，计算机无法承受；即使在空间上能勉强通过，运行的时间复杂度也极高，根本不可能在比赛规定的运行时间内计算出试题需要的结果，只能采用一种特殊数据结构——并查集来描述。
【例】、亲戚(relation)
【问题描述】 或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。在这种情况下，最好的帮手就是计算机。为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。
【输入格式】 输入由两部分组成。
第一部分以N，M开始。N为问题涉及的人的个数(1≤N≤20000)。这些人的编号为1,2,3,…, N。下面有M行(1≤M≤1 000 000)，每行有两个数ai, bi，表示已知ai和bi是亲戚。
第二部分以Q开始。以下Q行有Q个询问(1≤Q≤1 000 000)，每行为ci, di，表示询问ci和di是否为亲戚。
【输出格式】 对于每个询问ci, di，输出一行：若ci和di为亲戚，则输出“Yes”，否则输出“No”。
【输入样例】
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
【输出样例】
Yes
No
Yes
【算法分析】 将每个人抽象成为一个点，数据给出M个边的关系，两个人是亲戚的时候两点间有一条边。很自然的就得到了一个N个顶点M条边的图论模型，注意到传递关系，在图中一个连通块中的任意点之间都是亲戚。对于最后的Q个提问，即判断所提问的两个顶点是否在同一个连通块中。
用传统的思路，可以马上反应过来，对于输入的N个点M条边，找出连通块，然后进行判断。但这种实现思路首先必须保存M条边，然后再进行普通的遍历算法，效率显然不高。再进一步考虑，如果把题目的要求改一改，对于边和提问相间输入，即把题目改成：
第一行是N，M。N为问题涉及的人的个数(1≤N≤20000)。这些人的编号为1,2,3,…, N。下面有M行(1≤M≤2 000 000)，每行有三个数ki,ai, bi。ai, bi表示两个元素，ki为0或1，ki为1时表示这是一条边的信息，即ai, bi是亲戚关系；ki为0时表示是一个提问，根据此行以前所得到的信息，判断ai, bi是否亲戚，对于每条提问回答Yes或者No。
这个问题比原问题更复杂些，需要在任何时候回答提问的两个人的关系，并且对于信息提示还要能立即合并两个连通块。采用连通图思想显然在实现上就有所困难，因为要表示人与人之间的关系。
用集合的思路，对于每个人建立一个集合，开始的时候集合元素是这个人本身，表示开始时不知道任何人是他的亲戚。以后每次给出一个亲戚关系时，就将两个集合合并。这样实时地得到了在当前状态下的集合关系。如果有提问，即在当前得到的结果中看两元素是否属于同一集合。对于样例数据的解释如下图：
由图可以看出，操作是在集合的基础上进行的，没有必要保存所有的边， 而且每一步得到的划分方式是动态的。 那么，如何来实现以上的算法思想呢？我们就用到并查集。
1、什么叫并查集
并查集（union-find set）是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjoint set）。并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。 例如，有这样的问题：初始时n个元素分属不同的n个集合，通过不断的给出元素间的联系，要求实时的统计元素间的关系（是否存在直接或间接的联系）。这时就有了并查集的用武之地了。元素间是否有联系，只要判断两个元素是否属于同一个集合；而给出元素间的联系，建立这种联系，则只需合并两个元素各自所属的集合。这些操作都是并查集所提供的。 并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，数组实现、链表实现和树实现。一般用的比较多的是数组实现。
2、并查集支持的操作
并查集支持的操作 并查集的数据结构记录了一组分离的动态集合S={S1,S2,…,Sk}。每个集合通过一个代表加以识别，代表即该元素中的某个元素，哪一个成员被选做代表是无所谓的，重要的是：如果求某一动态集合的代表两次，且在两次请求间不修改集合，则两次得到的答案应该是相同的。 动态集合中的每一元素是由一个对象来表示的，设x表示一个对象，并查集的实现需要支持如下操作：
MAKE(x)：建立一个新的集合，其仅有的成员（同时就是代表）是x。由于各集合是分离的，要求x没有在其它集合中出现过。
UNIONN(x,y)：将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是Sx∪Sy的某个成员。一般来说，在不同的实现中通常都以Sx或者Sy的代表作为新集合的代表。此后，由新的集合S代替了原来的Sx和Sy。
FIND(x)：返回一个指向包含x的集合的代表。
# include <bits/stdc++.h>
using namespace std;
#define maxn 20001
int father[maxn];
int m,n,i,x,y,q;
int find(int x) // 查x所在集合编号
{
if (father[x] != x) return find(father[x]);
return x;
}
void Merge(int r1,int r2) // 将r2祖宗所在集合编号改为r1祖宗的编号.合并集合
{
r1 = find(r1);
r2 = find(r2);
if (r1 != r2) father[r2] = r1;
}
void pout() // 输出所有人的父亲编号
{
for (i = 1; i <= n; i++) printf("%2d",i);
cout<<endl;
for (i = 1; i <= n; i++) printf("%2d",father[i]);
cout<<endl;
}
int main()
{
cin >> n >> m>>q;
for (i = 1; i <= n; i++) father[i] = i; //初始化。一开始每个人所属的集合编号就是自己的编号
while(m--)
{
scanf("%d%d",&x,&y);
Merge(x,y);
pout();//
}
// for (i = 1; i <= q; i++)
// {
// scanf("%d%d",&x,&y);
// if (find(x) == find(y)) printf("Yes\n");
// else printf("No\n");
// }
return 0;
}
观察每次合并后father数组中的值
8 7 3 1 2 1 2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 3 4 1 2 3 4 5 6 7 8 1 1 3 3 5 6 7 8 5 6 1 2 3 4 5 6 7 8 1 1 3 3 5 5 7 8 7 8 1 2 3 4 5 6 7 8 1 1 3 3 5 5 7 7 1 3 1 2 3 4 5 6 7 8 1 1 1 3 5 5 7 7 6 7 1 2 3 4 5 6 7 8 1 1 1 3 5 5 5 7 4 5 1 2 3 4 5 6 7 8 1 1 1 3 1 5 5 7
观察最后一次合并
1 2 3 4 5 6 7 8 1 1 1 3 5 5 5 7
5的祖先是5，
4的父亲是3，3的父亲是1，所以4的祖先是1；
4 5 合并后5的父亲变成了1，但4的父亲还是3。
1 2 3 4 5 6 7 8
1 1 1 3 1 5 5 7
为了防止链过长影响查询效率，做个路径压缩，也就是找到祖先后，直接把祖先当成父亲。
# include <bits/stdc++.h>
using namespace std;
#define maxn 20001
int father[maxn];
int m,n,i,x,y,q;
int find(int x) // 查x所在集合编号 ,同时将x的父节点改为集合号（路径压缩）,提升查询效率。
{
if (father[x] != x) return father[x]=find(father[x]);
return x;
}
void Merge(int r1,int r2) // 将r2所在集合编号改为r1.合并集合
{
r1 = find(r1);
r2 = find(r2);
if (r1 != r2) father[r2] = r1;
}
void pout() // 输出所有人的父亲编号
{
for (i = 1; i <= n; i++) printf("%2d",i);
cout<<endl;
for (i = 1; i <= n; i++) printf("%2d",father[i]);
cout<<endl;
}
int main()
{
cin >> n >> m>>q;
for (i = 1; i <= n; i++) father[i] = i; //初始化。一开始每个人所属的集合编号就是自己的编号
while(m--)
{
scanf("%d%d",&x,&y);
Merge(x,y);
pout();//
}
// while(q--)
// {
// scanf("%d%d",&x,&y);
// if (find(x) == find(y)) printf("Yes\n");
// else printf("No\n");
// }
return 0;
8 7 3
1 2 1 2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 3 4 1 2 3 4 5 6 7 8 1 1 3 3 5 6 7 8 5 6 1 2 3 4 5 6 7 8 1 1 3 3 5 5 7 8 7 8 1 2 3 4 5 6 7 8 1 1 3 3 5 5 7 7 1 3 1 2 3 4 5 6 7 8 1 1 1 3 5 5 7 7 6 7 1 2 3 4 5 6 7 8 1 1 1 3 5 5 5 7 4 5 1 2 3 4 5 6 7 8 1 1 1 1 1 5 5 7
观察最后一次合并
1 2 3 4 5 6 7 8 1 1 1 3 5 5 5 7
5的父亲是5；
4的父亲是3，3的父亲是1，所以4的祖先是1；
4 5 合并（将5的祖先的父亲改为4的祖先的父亲）。5的父亲改为1，同时4的父亲也改为1了。这样提高了查询效率
1 2 3 4 5 6 7 8 1 1 1 1 1 5 5 7
标签：查集,r1,r2,int,元素,集合 From： https://www.cnblogs.com/flatte/p/17579638.html