数据结构-并查集

数据结构-并查集

并查集（Disjoint-Set）是一种可以动态维护若干个不重叠的集合，并支持合并与查询的数据结构。

get操作查询一个元素属于哪一个集合。

merge操作把两个集合合并成一个大集合。

//并查集的存储
int fa[N];
//并查集的初始化，时间复杂度O(n)
//设有n个元素，起初所有元素各自构成一个独立的集合，即有n棵1个点的树。
for(int i=1;i<=n;i++) fa[i]=i;
//并查集的get操作
//若x是树根，则x是集合代表，否则递归访问fa[x]直至根节点。
int get(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}
//并查集的merge操作
//合并元素x和元素y所在的集合，等价于让x的树根作为y的树根的子节点。
void merge(int x,int y)
{
    fa[get(x)]=get(y);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)