836. 合并集合
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 mm 个操作，操作共有两种：
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≤10^5
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
AC代码
#include <iostream>
using namespace std;
const int Ma=1000010;
int p[Ma];
//p[x]表示x的父亲节点;
int find(int x){
//每次递归是找x的父亲节点，直到x的父亲节点是它自己，就返回；
//假设 p[3] = 1，而 p[1] = 0，那么 3 的根节点就是 0。(动手推可以解决你写代码的50%问题)
if(p[x]!=x){
p[x]=find(p[x]);
}
return p[x];
}
int main(){
int n,m;
cin >> n >> m;
//循环的意义：在并查集中，每个元素都有一个父节点。最开始，每个元素的父节点是它自己。例如：
// p[0] = 0, p[1] = 1, p[2] = 2 .......;
for(int i=0;i<n;i++) p[i]=i;
char op;
int x,y;
while(m--){
cin >> op;
if(op=='M'){
cin >> x >> y;
//x指向y执行合并；
p[find(x)]=find(y);
}else{
cin >> x >> y;
//同一个祖先；
if(find(x) == find(y)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}
837. 连通块中点的数量
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 mm 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤10^5
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
AC代码 :
方法一：
#include <iostream>
#include <cstring>
using namespace std;
const int Ma=1000010;
int p[Ma],centre[Ma];
//p[x]是x的父亲节点；
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main(){
int n,m;
cin >> n >> m;
for(int i=0;i<n;i++){
//初始值都是父节点；
p[i]=i;
//每个初始节点中心为1；
centre[i]=1;
}
while(m--){
char op[2];
cin >> op;
//合并操作；
if(op[0]=='C'){
int x,y;
cin >> x >> y;
if(find(x)==find(y)) continue; //判断指向指向自己的情况，指向自己的中心节点就是1，不能加；
//这里纠结为什么是先加后结合；
//这里我们先加的话就相当于刚开始的根节点进行相加，y+x，如果先结合就是(y+x)+x; (y+x)结合，在判断两个根节点相加就错了；
centre[find(y)]+=centre[find(x)];
p[find(x)]=find(y); //让x的父亲节点指向y的父亲节点；
}else if(op[1]=='1'){
int x,y;
cin >> x >> y;
if(find(x)==find(y)){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}else{
int x;
cin >> x;
cout << centre[find(x)] << endl;
}
}
return 0;
}
AC代码：
方法二：
#include <iostream>
using namespace std;
const int N = 100010;
int n, m; 1 1
int p[N], cnt[N]; //cnt每个根节点都是1； A----B 就相当于 A合并B;这就是题目的：连通块中点的数量：2
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
cnt[i] = 1;
}
while (m -- )
{
string op;
int a, b;
cin >> op;
if (op == "C")
{
cin >> a >> b;
a = find(a), b = find(b); //方法二：这里就解决了一系列问题；
//提取a和b的根节点，如果不是同一个根节点，就相加，结合；
if (a != b)
{
cnt[b] += cnt[a]; //提前求出两个根节点；到时候要是有新的节点要插入到b中，直接++；
p[a] = b; //这样做，也就不用在纠结谁在前，谁在后了；都是独自判断各个根节点；
}
}
else if (op == "Q1")
{
cin >> a >> b;
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
AC代码：
JAVA：
import java.util.Scanner;
class Main {
static int n, m;
static final int MAX_VALUE = 1000010;
static int[] p = new int[MAX_VALUE]; // 父节点数组
static int[] center = new int[MAX_VALUE]; // 中心数组
private static int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]); // 路径压缩
}
return p[x];
}
public static void main(String[] args) {
Scanner op = new Scanner(System.in);
n = op.nextInt();
m = op.nextInt();
// 初始化节点
for (int i = 0; i < n; i++) {
p[i] = i;
center[i] = 1;
}
while (m-- > 0) {
String s = op.next();
char[] c = s.toCharArray();
if (c[0] == 'C') {
int x = op.nextInt();
int y = op.nextInt();
int a = find(x), b = find(y);
if (a != b) {
center[b] += center[a];
p[a] = b;
}
} else if (c[1] == '1') {
int x = op.nextInt();
int y = op.nextInt();
if (find(x) == find(y)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
} else {
int x = op.nextInt();
System.out.print(center[find(x)]);
}
}
op.close(); // 关闭Scanner
}
}