AcWing 836. 合并集合

合并集合 - 并查集

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int n, m;
int p[N];
//并查集里的father数组 存的是每个元素他的父节点是谁
int find(int x){//find x 返回x所在集合的编号 即返回x的祖宗节点
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) p[i] = i;
	while(m--){
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);
		if(op[0] == 'M') p[find(a)] = find(b);
		else{
			if(find(a) == find(b)) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

![[Pasted image 20221220130751.png]]

# 问题 2 的时间复杂度高？如何优化？

并查集的优化：当叶节点从x向上找找到祖宗节点后，直接将所有叶节点指向祖宗节点
即路径压缩（并查集在加完这个优化之后基本上就可以看成O(1)的时间复杂度了）

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int p[N];

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    
    return p[x];
}// 返回x的祖宗节点 + 路径压缩
//核心操作：如果x不是根节点的话 就让他的父节点 = 祖宗节点 然后返回他的父节点就可以了

int main(){
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) p[i] = i;
    
    while(m--){
        char op[2];
        //为甚么这里是op[2] 因为scanf有缺点：会读入空格和回车之类莫名其妙的字符 但是scanf读入字符串的时候会自动忽略空格和回车
        //因此如果用scanf读入一个字母的话建议读入成字符串的形式 因为这样可以帮助我们过滤掉空格和回车
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        
        if(op[0] == 'M') p[find(a)] = find(b);//让p[a]的父节点即a树直接插到b树下面
        else{
            if(find(a) == find(b)) puts("Yes");//判断两个节点是否在同一个集合里面 //因为find(a)返回的是a树的祖宗节点 //find(b)返回的是b树的祖宗节点 
            //如果两个祖宗节点一样的话就说明在一个集合里面否则就不在
            else puts("No");
        }
    }
    
    return 0;
}