连通块中点的数量-阿里云开发者社区

连通块中点的数量

2023-02-10 57

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 连通块中点的数量

为什么这个题题解这么少啊

是不是大家都太强不屑于做板子题啊

//来自算法基础课

维护连通块size的并查集

一、初始化

void init() {
for (int i=1; i<=n; i++) {
fa[i] = i;
size[i] = 1;
}
}

二、找祖源

int find(int x) {
if(fa[x]==x) return x;
else return fa[x] = find(fa[x]);
}

三、合并连通块

void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
size[y] += size[x];
}

四、询问是否连通

bool ask(int a,int b) {
return find(a)==find(b);
}

特别注意：

size只有祖节点的有意义

要特别注意所有处理size的地方，都要“归根结底”

完整CODE

#include<bits/stdc++.h>
#define read(x) scanf(“%d”,&x)
using namespace std;
const int N = 1e5+5;
int n,m,a,b,fa[N], size[N];
string act;
void init() {
for (int i=1; i<=n; i++) {
fa[i] = i;
size[i] = 1;
}
}
int find(int x) {
if(fa[x]==x) return x;
else return fa[x] = find(fa[x]);
}
void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
size[y] += size[x];
}
bool ask(int a,int b) {
return find(a)==find(b);
}
int main() {
read(n),read(m);
init();
while(m–) {
cin>>act;
if(act==“C”) {
read(a),read(b);
if(!ask(a,b)) merge(a,b);
} else if(act==“Q1”) {
read(a),read(b);
ask(a,b) ? printf(“Yes\n”) : printf(“No\n”);
} else {
read(a);
printf(“%d\n”,size[find(a)]);
}
}
return 0;
}