题目描述
给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
现在要进行m个操作，操作共有三种：
“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≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
算法1
(暴力枚举) $O(n^2)$
起始每次遇到并查集的题目，总会下意识的先去想想哈希。
但是哈希的合并那就逊色多了。不过这次也AC了。
计算相同集合里的个数要注意了，尽量在合并的时候注意次序，
序号小的统计记录不重复的记录下之后的所有大序号元素的个数。
序号大的元素记录里不要统计小序号元素个数，避免重复。
C++ 代码
// 000.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <map>
#include <set>
using namespace std;
/*
//并查集模板
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int get(int x)
{
return fa[x]==x?x:fa[x]=get(fa[x]);//路径压缩,防止链式结构
}
void merge(int x,int y)
{
fa[get(x)]=get(y);
}
给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
现在要进行m个操作，操作共有三种：
“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≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
*/
int n, m;
set<int> ss[100010];
int cnt[100010];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
ss[i].insert(i);
cnt[i] = 1;
}
for (int i = 0; i < m; i++) {
char op[10];
cin >> op;
if (op[0] == 'C') {
int a, b;
cin >> a >> b;
while (a != *ss[a].begin()) {
a = *ss[a].begin();
}
while (b != *ss[b].begin()) {
b = *ss[b].begin();
}
if(a !=b){
if(a < b){
cnt[a] += cnt[b];
ss[b].insert(a);
}
else{
cnt[b] += cnt[a];
ss[a].insert(b);
}
}
}
else if (op[0] == 'Q'&& op[1] == '1') {
int a; int b;
cin >> a >> b;
while (a != *ss[a].begin()) {
a = *ss[a].begin();
}
while (b != *ss[b].begin()) {
b = *ss[b].begin();
}
if (a == b) cout << "Yes" << endl;
else cout << "No" << endl;
}
else if (op[0] == 'Q'&& op[1] == '2') {
int a;
cin >> a;
while (a != *ss[a].begin()) {
a = *ss[a].begin();
}
cout << cnt[a] << endl;
}
}
}
算法2
正规并查集做法
同样的 相同集合元素个数的记录也是要注意
序号小的统计记录不重复的记录下之后的所有大序号元素的个数。
序号大的元素记录里不要统计小序号元素个数，避免重复。
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int p[N],siz[N];
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;
siz[i] = 1;
}
while(m--){
string op;
int a,b;
cin >> op;
if(op == "C"){
cin >> a >> b;
a= find(a); b = find(b);
if(a != b){
p[a] = b;
siz[b] += siz[a];
}
}else if( op == "Q1"){
cin >> a>> b;
if(find(a) == find(b)) cout << "Yes" << endl;
else cout << "No"<< endl;
}else{
cin >> a;
cout << siz[find(a)] << endl;
}
}
return 0;
}
