一般处理的问题
1.将两个集合合并
2.询问两个元素是否在一个集合当中
如果是暴力做法 数组存储每个元素属于哪一个集合
1.
belong[x]=a
if(belong[x]=belong[y]) O(1)
2.如果想合并 极其麻烦 元素多了就寄了
基本原理
用树的形式维护每一个集合 树根的编号就是集合的编号
每个节点存储它的父节点p[x]表示x的父节点
1.
将一棵树插到另一棵树
px是x的集合编号 py是y的集合编号 合并就是p[x]=y
- 求某个点属于哪个集合 通过其父节点
求x的集合编号 while(p[x]!=x) x=p[x]; 路径压缩优化 一旦找到根节点 整个路径上所有结点直接指向根节点
[并查集] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m;
int p[N]; //存父节点
int find(int x) //返回x的祖宗节点+路径压缩
{
if(p[x]==x) return x;//没错 就两行 如果x不是根节点 就让x的父节点等于它的祖宗节点
return p[x]=find(p[x]); //递归将路径上所有结点的父节点都是根节点
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op[2];
int a,b;
cin>>op>>a>>b;
if(op[0]=='M') p[find(a)]=find(b) //合并操作 让a的祖宗节点的父亲等于b的祖宗节点 相当于插入了
else //判断是否在同一个集合里
{
if(find(a)==find(b)) puts("Yes")
else puts("No")
}
}
}
|
acwing 837
其实思路十分相近 所谓连通块可以直接用集合来维护 只需模板代码稍作改变
主要问题是怎么维护size 也就是集合里元素数量
[连通块中点的数量] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m;
int p[N],size[N]; //每一个集合里点的数量
int find(int x)
{
if(p[x]==x) return x;
return p[x]=find(p[x])
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
p[i]=i;
size[i]=1;
}
while(m--)
{
char op[5];
int a,b;
cin>>op;
if(op[0]=='C')//合并
{
cin>>a>>b;
if(find(a)==find(b)) continue;//此题有自己连自己的情况 需要特判
size[find(b)]+=size[find(a)];
p[find(a)]=find(b);
}
else if(op[1]=='1')
{
cin>>a>>b;
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
else // 问数量
{
cin>>a;
cout<<size[(find(a))];
}
}
}
|
