题目描述
其实就是用并查集判断啦 模板题哟
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
C++ 代码
#define test "AcWing_联通块点的数量.txt"
#define MAXN 100005
#include <string.h>
#include <iostream>
using namespace std;
int pre[MAXN], sum[MAXN], n, m;
void init() {
for(int i=1; i<=n; i++)
pre[i] = -1, sum[i] = 1;
}
int fa(int x) {
int ret = x;
while(pre[ret] != -1)
ret = pre[ret];
if(ret != x)
pre[x] = ret;
return ret;
}
bool union_xy(int x, int y) {
int rx = fa(x), ry = fa(y);
if(rx != ry) {
sum[rx] += sum[ry];
pre[ry] = rx;
return true;
}
return false;
}
int main(void) {
freopen(test, "r", stdin);
for( ; EOF != scanf("%d %d", &n, &m); ) {
init();
for( ; m--; ) {
char c[4];
int x, y;
scanf("%s", c);
if(c[0] == 'C') {
scanf("%d %d", &x, &y);
union_xy(x, y);
} else if(c[1] == '1') {
scanf("%d %d", &x, &y);
printf("%s\n", fa(x)==fa(y) ? "Yes" : "No");
} else if(c[1] == '2') {
scanf("%d", &x);
printf("%d\n", sum[fa(x)]);
}
}
}
return 0;
}
----------
### 算法2
##### (暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
#### C++ 代码
blablabla
```