大家都有亲戚朋友对不对。
来让我们看两道题
亲戚 朋友
显然我们需要并查集。
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));//取小明/小红认识的人中最少的（你不能让两男或者两女在一起，更不能让多余的人自己在一起，这是规定） }
转载于:https://www.cnblogs.com/lcez56jsy/p/10732474.html
相关资源：数据结构—成绩单生成器