在许多实际应用场景中，我们需要对元素进行分组，并且在这些分组中进行查询和修改操作。比如，在图论中，我们需要将节点按照连通性进行分组，以便进行最小生成树、最短路径等算法；在计算机视觉中，我们需要将像素进行分组，以便进行图像分割和对象识别等任务。而并查集正是为了解决这些问题而被提出来的一种数据结构。
概念
并查集（Disjoint Set）是一种用于处理元素分组的数据结构，通常用于解决一些与等价关系有关的问题，比如连通性的判断、最小生成树算法中的边的合并等。
并查集中的每个元素都属于一个集合，每个集合都有一个代表元素（也称为根节点），代表元素可以用来表示整个集合。并查集支持三个基本操作：
1.MakeSet(x)：创建一个只包含元素 x 的新集合；
2.Find(x)：返回元素 x 所属的集合的代表元素；
3.Union(x, y)：将元素 x 和 y 所属的集合合并成一个新集合。
其中，Find 操作可以使用路径压缩（Path Compression）和按秩合并（Union by Rank）优化，以提高查询效率。
并查集的应用非常广泛，比如在图论算法中求解连通性、求解最小生成树等问题时都会用到。
伪代码
// 初始化并查集，每个元素单独成集合 function MakeSet(x) x.parent = x x.rank = 0 // 查找元素所属的集合（根节点），并进行路径压缩 function Find(x) if x.parent != x x.parent = Find(x.parent) // 路径压缩：将x的父节点设为根节点 return x.parent // 合并两个集合，按秩合并 function Union(x, y) xRoot = Find(x) yRoot = Find(y) if xRoot == yRoot return // 已经在同一个集合中，无需合并 if xRoot.rank < yRoot.rank xRoot.parent = yRoot else if xRoot.rank > yRoot.rank yRoot.parent = xRoot else yRoot.parent = xRoot xRoot.rank = xRoot.rank + 1
接下来，让我们进行并查集的相关练习。
选择题
1.
选B
2.
解析： 1 -4 1 1 -3 4 4 8 -2 0 1 2 3 4 5 6 7 8 1对应-4，则1是根节点且有4个子孙 又因为0、2、3都对应1 所以 1 0 2 3 null 4对应-3，则4是根节点且有3个子孙 又因为5、6都对应4 所以 4 5 6 null 8对应-2，则8是根节点且有2个子孙 又因为7对应8 所以 8 7 null 将6与8所在的集合合并，且小集合合并到大集合 则 4 5 6 8 7 null 所以树根是4，对应的编号是-5（-表示树根，5表示4的子孙个数）
3.
可以画出来对应的树 然后把小树连到大树上 接着从1到7遍历 如果有父节点，给出父节点的值 如果它本身是根节点，则给出负号和子孙个数
填空题
编程题
7-1 朋友圈
某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。
输入格式:
输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：
第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi
输出格式:
输出给出一个整数，表示在最大朋友圈中有多少人。
输入样例:
7 4 3 1 2 3 2 1 4 3 5 6 7 1 6
输出样例:
4
#include<stdio.h> int a[30001]; // 定义数组a，用于存储并查集的父节点信息 int search(int b){ // 查找元素所属的集合（根节点） if(a[b]<0){ // 如果a[b]小于0，说明b是根节点 return b; // 返回b作为集合的代表元素 }else{ return search(a[b]); // 否则递归查找父节点，直到找到根节点 } } void function(int m,int n){ // 合并两个集合 int x,y; x=search(m); // 查找m所属的集合（根节点） y=search(n); // 查找n所属的集合（根节点） if(x!=y){ // 如果m和n不在同一个集合中 a[x]+=a[y]; // 将集合y的大小加到集合x上 a[y]=x; // 将集合y的父节点指向集合x } } int main(){ int m,n; scanf("%d %d",&n,&m); // 输入学生数量n和关系数量m int i; for(i=0;i<=n;i++){ // 初始化并查集，每个元素单独成集合 a[i]=-1; // 初始时每个元素的父节点为自身，且集合大小为1 } int stu,j,num,num1; for(i=0;i<m;i++){ // 处理每组关系 scanf("%d",&stu); // 输入每组关系中学生的数量 for(j=0;j<stu;j++){ // 输入每组关系中的学生编号 scanf("%d",&num); if(j==0){ num1=num; // 记录第一个学生的编号 }else{ function(num1,num); // 合并这组关系中的学生 } } } int min; min=a[1]; for(i=2;i<n;i++){ // 找到集合中最小的负数，作为集合大小的相反数 if(min>a[i]){ min=a[i]; } } printf("%d",-min); // 输出最少需要分成的组数 }
R7-1 笛卡尔树
笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树，即结点左子树的所有K1值都比该结点的K1值小，右子树则大。其次所有结点的K2关键字满足优先队列（不妨设为最小堆）的顺序要求，即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树，请判断该树是否笛卡尔树。
输入格式:
输入首先给出正整数N（≤1000），为树中结点的个数。随后N行，每行给出一个结点的信息，包括：结点的K1值、K2值、左孩子结点编号、右孩子结点编号。设结点从0~(N-1)顺序编号。若某结点不存在孩子结点，则该位置给出−1。
输出格式:
输出YES如果该树是一棵笛卡尔树；否则输出NO。
输入样例1:
6 8 27 5 1 9 40 -1 -1 10 20 0 3 12 21 -1 4 15 22 -1 -1 5 35 -1 -1
输出样例1:
YES
输入样例2:
6 8 27 5 1 9 40 -1 -1 10 20 0 3 12 11 -1 4 15 22 -1 -1 50 35 -1 -1
输出样例2:
NO
#include<bits/stdc++.h> using namespace std; struct Node{ int k1; int k2; int left_c; int right_c; }a[1200]; // 定义结构体Node，表示二叉树的每个节点 int root,flag=1; // 定义变量root表示根节点，flag表示是否符合条件 int b[1200]; // 定义数组b，用于标记每个节点是否有左右孩子 int zhongxu[1200],cnt=0; // 定义数组zhongxu，存储中序遍历序列，cnt为元素数量 void midorder(int root){ // 中序遍历二叉树 if(root!=-1){ // 如果根节点不为空 midorder(a[root].left_c); // 遍历左子树 zhongxu[cnt]=a[root].k1; // 将当前节点的值存入中序遍历序列中 cnt++; // 记录元素数量 midorder(a[root].right_c); // 遍历右子树 } } void judgeheap(int root){ // 判断是否为堆 int left,right; if(a[root].left_c!=-1){ // 如果左孩子存在 left=a[root].left_c; if(a[left].k2<a[root].k2){ // 如果左孩子的值小于根节点的值 flag=0; // 不符合堆的条件 return ; } judgeheap(left); // 递归遍历左子树 } if(a[root].right_c!=-1){ // 如果右孩子存在 right=a[root].right_c; if(a[right].k2<a[root].k2){ // 如果右孩子的值小于根节点的值 flag=0; // 不符合堆的条件 return ; } judgeheap(right); // 递归遍历右子树 } } int main() { int n; cin>>n; // 输入节点数量n int i,K1,K2,Left,Right; memset(b,0,sizeof(b)); // 初始化数组b，全部置为0 for(i=0;i<n;i++) // 处理每个节点的信息 { scanf("%d %d %d %d",&K1,&K2,&Left,&Right); // 输入节点的值、权值、左右孩子的编号 a[i].k1=K1; // 将节点的值存入结构体 a[i].k2=K2; // 将节点的权值存入结构体 a[i].left_c=Left; // 将左孩子编号存入结构体 a[i].right_c=Right; // 将右孩子编号存入结构体 if(Left!=-1) // 如果左孩子存在 b[Left]=1; // 标记左孩子编号为1 if(Right!=-1) // 如果右孩子存在 b[Right]=1; // 标记右孩子编号为1 } for(i=0;i<n;i++){ // 找到根节点 if(b[i]==0){ // 如果节点没有左右孩子，说明其为根节点 root=i; break; } } midorder(root); // 中序遍历二叉树，得到中序遍历序列 for(i=1;i<cnt;i++){ // 判断是否为完全二叉树 if(zhongxu[i]<=zhongxu[i-1]){ // 如果中序遍历序列不是单调递增的 flag=0; // 不符合完全二叉树的条件 break; } } judgeheap(root); // 判断是否为堆 if(flag) // 如果符合条件 printf("YES\n"); // 输出YES else printf("NO\n"); // 输出NO return 0; }
R7-2 部落
在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] ⋯ P[K]
其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。
之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。
输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。
输入样例：
4 3 10 1 2 2 3 4 4 1 5 7 8 3 9 6 4 2 10 5 3 7
输出样例：
10 2 Y N
#include<iostream> #include<set> #include<cstdio> using namespace std; int pre[10010]; // 定义数组pre，用于存储每个元素的祖先 int find(int x){ // 查找操作，返回x的祖先 if(pre[x]==x) return x; return pre[x]=find(pre[x]); } void unite(int x,int y){ // 合并操作，将x所在集合和y所在集合合并 x=find(x); y=find(y); if(x!=y) pre[x]=y; } int main(){ int n,x,y,m,a; for(int i=1;i<=10000;i++) pre[i]=i; // 初始化每个元素的祖先为自身 set<int>s,ss; // 定义两个set容器s和ss，分别用于存储所有元素和合并后的元素 cin>>n; // 输入集合数量n while(n--){ // 处理每个集合 cin>>m; // 输入集合中元素数量m cin>>x; // 输入第一个元素的值 s.insert(x); // 将第一个元素插入到集合s中 for(int i=1;i<m;i++){ // 处理集合中的其他元素 cin>>y; // 输入元素的值 s.insert(y); // 将元素插入到集合s中 unite(x,y); // 将元素x和元素y所在的集合合并 } } set<int>::iterator it; // 定义迭代器it，用于遍历集合s中的元素 for(it=s.begin();it!=s.end();it++) // 遍历集合s中的元素 ss.insert(find(*it)); // 将每个元素的祖先插入到集合ss中 printf("%d %d\n",s.size(),ss.size()); // 输出集合s的大小和集合ss的大小 cin>>a; // 输入查询次数a while(a--){ // 处理每次查询 cin>>x>>y; // 输入要查询的两个元素 if(find(x)==find(y)) // 如果两个元素的祖先相同 puts("Y"); // 输出Y else puts("N"); // 输出N } return 0; }
R7-3 秀恩爱分得快
古人云：秀恩爱，分得快。
互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？
输入格式：
输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：
K P[1] ... P[K]
其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。
输出格式：
首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB。但如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。
输入样例 1：
10 4 4 -1 2 -3 4 4 2 -3 -5 -6 3 2 4 -5 3 -6 0 2 -3 2
输出样例 1：
-3 2 2 -5 2 -6
输入样例 2：
4 4 4 -1 2 -3 0 2 0 -3 2 2 -3 2 -1 2 -3 2
输出样例 2：
-3 2
#include<bits/stdc++.h> using namespace std; #define ll long long #define rep(i,a,b) for(int i=(a);i<(b);++i) #define maxn 4019 int n,m,k[maxn],A,B,sexa,sexb; //人数，图片数，每张图片的人数数组，两个人的编号，两个人的性别 int fu[maxn],pic[maxn][maxn],pwa[maxn],pwb[maxn]; //人的性别数组，图片中的人物编号数组，用于计算亲密度的临时数组 double pa[maxn],pb[maxn]; //与A、B的亲密度数组 vector<int>ans1,ans2; //存储亲密度最高的人的编号 struct gg { int id; //人的编号 double v; //与A或B的亲密程度 } p1[maxn],p2[maxn]; //用于排序的临时结构体数组 //读取带负号的字符串并转换为整数 int read(char*str,int ans,int *fu_) { if(str[0]=='-') { int len=strlen(str); rep(t,1,len) ans=ans*10+str[t]-'0'; *fu_=-1; //标记为负数 } else { int len=strlen(str); rep(t,0,len) ans=ans*10+str[t]-'0'; *fu_=0; //标记为非负数 } return ans; } //根据性别计算与A或B的亲密度 void getpwith_(int index,int row) { memset(pwa,0,sizeof(pwa)); //清空临时数组 int sex=index==1?sexa:sexb; //根据index确定性别 rep(j,0,k[row]) { int peo=pic[row][j]; if(fu[peo]!=sex) //与A或B的性别不同的人，亲密度加1 { if(index) pwa[peo]=1; else pwb[peo]=1; } } } //比较函数，用于排序 int cmp(gg x,gg y) { if(x.v!=y.v) return x.v>y.v; return x.id<y.id; } int main() { scanf("%d%d",&n,&m); //读取人数和图片数 rep(i,0,m) { scanf("%d",&k[i]); //读取每张图片中的人数 char str[maxn]; //(1)读取pic[][]:存储出现过的每张图片里的具体人物编号和性别 rep(j,0,k[i]) { scanf("%s",str); //读取多位数 int fu_; pic[i][j]=read(str,pic[i][j],&fu_); //读取人物编号并标记性别 fu[pic[i][j]]=fu_; //记录人的性别 } } char AA[maxn],BB[maxn]; scanf("%s%s",AA,BB); //读取两个人的编号字符串 A=read(AA,0,&sexa); //将字符串转换为整数，并记录性别 B=read(BB,0,&sexb); /*当某个人和谁的好感度都是0，这时候只输出所有异性*/ rep(i,0,n){ if(fu[i]==sexa) pa[i]+=-1; //当与A的亲密度为0时，将其置为-1 if(fu[i]==sexb) pb[i]+=-1; //当与B的亲密度为0时，将其置为-1 } //(2)计算flaga,flagb(局部变量):标记计算m张图片里是否出现过A,B rep(i,0,m) { int flaga=0; int flagb=0; rep(j,0,k[i]) { if(pic[i][j]==A) flaga=1; //标记A在当前图片中出现过 if(pic[i][j]==B) flagb=1; //标记B在当前图片中出现过 } if(flaga) //计算A在局部和每个人同框的次数 { getpwith_(1,i); //计算与A的亲密度 rep(j,0,k[i]) pa[pic[i][j]]+=pwa[pic[i][j]]/double(k[i]); //累加亲密度 } if(flagb)//计算B在局部和每个人同框的次数 { getpwith_(0,i); //计算与B的亲密度 rep(j,0,k[i]) pb[pic[i][j]]+=pwb[pic[i][j]]/double(k[i]); //累加亲密度 } } rep(i,0,n) p1[i].id=i,p1[i].v=pa[i],p2[i].id=i,p2[i].v=pb[i]; //初始化结构体数组 sort(p1,p1+n,cmp); //按亲密度排序 sort(p2,p2+n,cmp); double maxa=p1[0].v; //A的最大亲密度 rep(i,0,n) { if(p1[i].v!=maxa) break; else ans1.push_back(p1[i].id); //将亲密度最高的人的编号存入ans1 } double maxb=p2[0].v; //B的最大亲密度 rep(i,0,n) { if(p2[i].v!=maxb) break; else ans2.push_back(p2[i].id); //将亲密度最高的人的编号存入ans2 } int len1=ans1.size(); int f1=0; rep(i,0,len1) { if(pa[ans1[i]]==pa[B]) //如果与B的亲密度与A的亲密度相同，则标记f1 f1=1; } int len2=ans2.size(); int f2=0; rep(i,0,len2) { if(pb[ans2[i]]==pb[A]) //如果与A的亲密度与B的亲密度相同，则标记f2 f2=1; } if(f1&&f2) //如果同时满足与A和B的亲密度相同的人存在，输出两个人的编号 { if(sexa==-1) cout<<'-'<<A<<" "; else cout<<A<<" "; if(sexb==-1) cout<<'-'<<B<<endl; else cout<<B<<endl; } else //否则，分别输出与A和B亲密度最高的人的编号 { rep(i,0,len1) { if(sexa==-1) cout<<'-'<<A<<" "; else cout<<A<<" "; if(fu[ans1[i]]==-1) cout<<'-'<<ans1[i]<<endl; else cout<<ans1[i]<<endl; } rep(i,0,len2) { if(sexb==-1) cout<<'-'<<B<<" "; else cout<<B<<" "; if(fu[ans2[i]]==-1) cout<<'-'<<ans2[i]<<endl; else cout<<ans2[i]<<endl; } } return 0; }
以上就是并查集的知识点及相关练习了，在下一篇文章中我们将学习图的相关知识点。
