北京正规网站建设经历,学做网站培训,成都宅天下装饰公司口碑,扬州招标工程建设信息网文章目录 QuestionIdeasCode Question
一共有 n 个数#xff0c;编号是 1∼n #xff0c;最开始每个数各自在一个集合中。
现在要进行 m 个操作#xff0c;操作共有两种#xff1a;
M a b#xff0c;将编号为 a 和 b 的两个数所在的集合合并#xff0c;如果两个数已经… 文章目录 QuestionIdeasCode Question
一共有 n 个数编号是 1∼n 最开始每个数各自在一个集合中。
现在要进行 m 个操作操作共有两种
M a b将编号为 a 和 b 的两个数所在的集合合并如果两个数已经在同一个集合中则忽略这个操作 Q a b询问编号为 a 和 b 的两个数是否在同一个集合中 输入格式 第一行输入整数 n 和 m 。
接下来 m 行每行包含一个操作指令指令为 M a b 或 Q a b 中的一种。
输出格式 对于每个询问指令 Q a b都要输出一个结果如果 a 和 b 在同一集合内则输出 Yes否则输出 No。
每个结果占一行。
数据范围 1≤n,m≤105 输入样例 4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4 输出样例 Yes No Yes
Ideas
并查集的作用
判断两个元素是否在一个集合中快速合并两个集合
Code
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1e5 10;
int p[N]; // 存储每个节点的父节点// 返回x的根节点
int find(int x){ // 查找根节点 路径压缩时间复杂度近似于O(1)if (p[x] ! x) // 只有根节点的父节点等于本身即 p[x] xp[x] find(p[x]);return p[x];
}
int main()
{int n, m;cin n m;for (int i 1; i n; i ) p[i] i; // 编号从1开始while (m -- ){char op[2];int a, b;cin op;cin a b;if (*op M){p[find(a)] find(b); // 将a合并到b结合下即a的根节点成为b的孩子}else{if (find(a) find(b)) // 查找a和b所属的集合puts(Yes);elseputs(No);} }return 0;
}
