题解：AcWing 6058 亲戚

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：6058. 亲戚 - AcWing题库

【题目描述】

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。

规定：

• 和 是亲戚， 和 是亲戚，那么 和 也是亲戚。
• 如果 是亲戚，那么 的亲戚都是 的亲戚， 的亲戚也都是 的亲戚。

具体来说，一共涉及到n nn个人（编号1 ∼ n 1\sim n1∼n），接下来将依次进行m mm个操作，操作分为以下两种：

• M a b，表示告知你a aa和b bb具有亲戚关系。
• Q a，表示向你询问，根据此前已经给定的所有信息，可以确定的a aa所在的家族的人数。

【输入】

第一行包含两个整数n , m n,mn,m。

接下来m mm行，每行包含一个操作信息，格式如题面描述。

【输出】

对于每个Q a操作，输出一行结果，一个整数，表示当时可以确定的a aa所在的家族的人数。

【输入样例】

5 10 M 3 2 Q 4 M 1 2 Q 4 M 3 2 Q 1 M 3 1 Q 5 M 4 2 Q 4

【输出样例】

1 1 3 1 4

【算法标签】

#并查集#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineN1000005intfa[N];// 并查集父节点数组intpeoNum[N];// peoNum[i]: 以i为根结点的集合的元素个数// 初始化并查集voidinitFa(intn){for(inti=1;i<=n;++i){fa[i]=i;// 每个结点初始化为自己的父节点peoNum[i]=1;// 每个集合初始大小为1}}// 查找根节点（带路径压缩）intfind(intx){if(x==fa[x])// 如果x是自己的父节点{returnx;// 返回x}else{returnfa[x]=find(fa[x]);// 递归查找并路径压缩}}// 合并两个集合voidmerge(inti,intj){intx=find(i);// i的根节点inty=find(j);// j的根节点if(x==y)// 如果x, y已经在一个集合内，直接返回{return;}fa[x]=y;// x的双亲设为ypeoNum[y]+=peoNum[x];// 合并集合大小}intmain(){ios::sync_with_stdio(false);// 关闭C++与C输入输出同步cin.tie(nullptr);// 解绑cin和cout，加速输入charc;// 操作类型intn,m,a,b;// n: 人数, m: 操作数, a,b: 操作参数cin>>n>>m;// 输入人数和操作数initFa(n);// 初始化并查集for(inti=1;i<=m;++i)// 处理每个操作{cin>>c;// 输入操作类型if(c=='M')// 合并操作{cin>>a>>b;merge(a,b);// 合并a,b所在的集合}else// c == 'Q'，查询操作{cin>>a;cout<<peoNum[find(a)]<<'\n';// 输出a所在集合的人数}}return0;// 程序正常结束}

【运行结果】

5 10 M 3 2 Q 4 1 M 1 2 Q 4 1 M 3 2 Q 1 3M 3 1 Q 5 1 M 4 2 Q 4