关键词：
大家都有亲戚朋友对不对。
来让我们看两道题
显然我们需要并查集。
So,什么是并查集？
并，就是合并关系（也就是认祖宗）。查，就是查找关系（就是看祖宗是不是一个人）。集，是因为它是个集合。
并查集怎么写呢？
前面说过要认祖宗，我们就有了一个father[i]，来记录每个i的祖宗。（以下简写为fa[i]）。
当数据给出两个人i,j的关系时，我们就把i和j并起来，即让j认i为祖宗。（反过来也行）。
要查找时，就判断两人的祖宗是否相同就行了。我们还缺一步：找爹。
怎么实现呢？看代码吧
//初始化 int fa[10001]; int main() cin>>n; for(int i=1;i<=n;i++) fa[i]=i;//一开始所有人的爹都是自己 //找爹 int find(int x) if(fa[x]==x)return x;//如果爹是自己，就返回自己 return find(fa[x]);//如果不是，就一直找 //合并 void unionn(int x,int y) x=find(x);y=find(y); fa[y]=fa[x];//这里让y的爹认x的爹为爹效果和让y认x当爹是一样的
这里的find会被毒瘤数据卡到超时，所以我们有个优化
int find(int x) if(fa[x]!=x)fa[x]=find(fa[x]);//这样优化后x的爹，爷爷...都认了根节点的祖宗了 return fa[x];
好了并查集讲完了233
我们回到开头那两道题
亲戚比较友善（毕竟是亲戚），只要改下输入输出就行了。
代码如下：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> int n,m,p,fa[5001]; int find(int x) if(fa[x]!=x)fa[x]=find(fa[x]); return fa[x]; void unionn(int x,int y) int xx=find(x),yy=find(y); fa[yy]=xx; int main() scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) int x,y; scanf("%d%d",&x,&y); if(find(x)!=find(y)) unionn(x,y); for(int i=1;i<=p;i++) int x,y; scanf("%d%d",&x,&y); if(find(x)==find(y)) printf("Yes\\n"); else printf("No\\n");//千万别手残都敲成大写字母！！！
朋友这道题，其实是道语文题
我们看下样例
发现一个规律：男生和女生中，编号对应且和小明/小红认识的人可以配成一对
但是事实并不是这样（我会告诉你我在这卡了n遍？）
事实是只要认识小明和小红，就能配成一对
跳过坑，就是题解
//因为女生是负数，所以我们把女生编号取负后放入另一个数组里 #include<iostream> #include<cstdio> #include<cmath> using namespace std; int faman[20001],fawo[20001];//fawo[i]就是女生的数组 int n,m,p,q; int findm(int x) if(faman[x]!=x)faman[x]=findm(faman[x]); return faman[x]; int findw(int x) if(fawo[x]!=x)fawo[x]=findw(fawo[x]); return fawo[x]; void um(int x,int y) x=faman[x];y=faman[y]; faman[y]=x; void uw(int x,int y) x=fawo[x];y=fawo[y]; fawo[y]=x; int main() scanf("%d%d%d%d",&n,&m,&p,&q); for(int i=1;i<=n;i++) faman[i]=i; for(int i=1;i<=m;i++) fawo[i]=i; for(int i=1;i<=p;i++) int x,y; scanf("%d%d",&x,&y); if(findm(x)!=findm(y)) um(x,y); for(int i=1;i<=q;i++) int x,y; scanf("%d%d",&x,&y); x=-x;y=-y;//因为这里女生是负数，所以要取负 if(findw(x)!=findw(y)) uw(x,y); int ansm=0,answ=0; int k=max(n,m); for(int i=1;i<=n;i++) if(findm(i)==findm(1))ansm++; for(int i=1;i<=m;i++) if(findw(i)==findw(1)) answ++; printf("%d",min(ansm,answ));//取小明/小红认识的人中最少的（你不能让两男或者两女在一起，更不能让多余的人自己在一起，这是规定）
golang并查集(代码片段)
并查集p3367模板并查集(代码片段)
P3367【模板】并查集#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>usingnamespacestd;intn,m,zi,xi,yi;intfather[10001] 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集... 查看详情
并查集——新手学习记录(代码片段)
好吧，什么垃圾并查集，并查集什么的都是铁憨憨<+__+>现在开始复习回忆：（新手，有错误望指正）什么叫做并查集，并查集就是一个集合问题，其实最主要的就是知道并查集是一个求解集合数目的问题，具体的操作方法有... 查看详情
并查集原理分析(代码片段)
文章目录1.并查集是什么2.并查集性质3.并查集可以解决的问题4.并查集模板5.并查集的应用1.并查集是什么在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时**，每个元素自成一个单元素集合**... 查看详情
数据结构--并查集(代码片段)
并查集并查集原理并查集实现并查集原理在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要... 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情
并查集(代码片段)
本文参考了【算法】并查集（DisjointSet）和并查集详解并查集原理并查集是一种用于处理不相交集合之间合并问题的数据结构，例如求连通子图、判断是否存在环、求最小生成树等。以判断图中是否有环为例，下图是一个无向图... 查看详情
dzyloveschemistry（并查集）(代码片段)
题目：（??，最近净做并查集了还一道难的都不会）DZYloveschemistry,andheenjoysmixingchemicals.DZYhasnchemicals,andmpairsofthemwillreact.Hewantstopourthesechemicalsintoatesttube,andheneedstopourtheminonebyone,inanyorder.Let‘sc 查看详情
树的应用——并查集及实现代码(代码片段)
文章目录什么是并查集亲戚问题并查集的实现改进——路径压缩进一步改进——合并并查集的用途什么是并查集 并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。常常在使用... 查看详情
并查集(入门)(代码片段)
首先先看一道很简单的并查集的题目：https://vjudge.net/contest/297398#problem/A这道题就是让你判断两两城镇之间是否联通 如果不联通就要修建一条道路 就我的理解来说，如果单独使用并查集就是为了合并有相同根结点(或者理... 查看详情
并查集(代码片段)
/*并查集*/#include<stdio.h>int*a;int*sz;intcount;//thenumberofconnectedcomponent//uniontwoconnectedcomponentswithweightsvoidunion_two_points(intp,intq)inti=root(p);intj=root(q);if(i==j)return;if(s 查看详情
并查集(代码片段)
...们看两道题 亲戚 朋友 显然我们需要并查集。 So,什么是并查集？ 并，就是合并关系（也就是认祖宗）。查，就是查找关系（就是看祖宗是不是一个人）。集，是因为它是个集合。 并查集怎么写呢... 查看详情
树--12---并查集(代码片段)
文章目录并查集并查集是一种树型的数据结构并查集结构1.并查集的实现API设计UF(intN)构造方法实现union(intp,intq)合并方法实现代码：测试：案例1:计算机网诺连接2.UF_Tree算法优化eleAndGourp数组API设计find(intp)查询方法实现unio... 查看详情
详解并查集(代码片段)
文章目录并查集原理并查集实现并查集应用并查集原理在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。... 查看详情
算法笔记：并查集(代码片段)
1并查集介绍 并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素... 查看详情
带权并查集&&并查集(代码片段)
并查集一般的并查集主要记录节点之间的链接关系，而没有其他的具体的信息，仅仅代表某个节点与其父节点之间存在联系，它多用来判断图的连通性主要操作有：初始化把每个点所在集合初始化为其自身。通常来说，这个步骤... 查看详情