并查集(树

并查集定义

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）

初始化

1
2
3
4
5
6
7
//定义数组，记忆每个节点对应的父节点
int fa[N];
for (int i = 1; i <= N - 1; i++)
{
  //初始时，每个节点的父节点就是自己本身
  fa[i] = i;
}

定义 find 函数，用于寻找某个节点的根节点（就是父节点的父节点的父。。。。。

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
//非递归写法
int find(int x)
{
  while (fa[x] != x)
  {
      x = fa[x];
  }
  return x;
}

//递归写法
int find(int x)
{
  if (fa[x] == x) return x;
  else
  {
    return find(fa[x]);
  }
}

//简化写法
int find(int x)
{
  return fa[x] == x ? x : find(fa[x]);
}

定义 join 合并函数，用于将两个树合并在一起，使他们拥有同一个根

1
2
3
4
5
6
7
8
//定义合并函数，将 x 所在树与 y 所在树合并一起
void join(int x, int y)
{
  int fx = find(x);
  int fy = find(y);
  if (fx != fy)
    fa[fx] = fy;
}

并查集优化

每次查找树中元素都是由根向下寻找，如果树的高度减小，搜索速度会加快，下面给出两种优化方法

一.路径压缩

每次查找某个节点的根时，在结束时顺便将这个节点直接指向根，使得他的父节点就是根（优化 find 函数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find(int x)
{
  if (fa[x] == x) return x;
  else
  {
    fa[x] = find(fa[x]);
    return fa[x];
  }
}

//简化代码
int find(int x)
{
  return fa[x] == x ? x : fa[x] = find(fa[x]);
}

二.按秩合并（加权标记）

秩指的就是树的高度，给树每个节点添加一个权值，用于表示该节点所在树中的高度，这样一来，在合并操作的时候就能通过这个权值的大小来决定谁当谁的上级

这样做有什么好处呢？你想啊，现在假如要将两个数合并，你为了后续搜索变快，是不是想要将树的高度尽可能变小，那么是 矮的树作高的树的父亲 还是 高的树作矮的树的父亲 哪个最终树的高度更小呢？显然是后者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//rank 用来记录每个节点所在树中的高度，那么 根的rank 就是树的高度啦
int rank[N];
void join(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y) return ;
    //rank 大的树作 rank小的树 的父亲
    if(rank[x]>rank[y]) fa[y]=x;
    else
    {
        if(rank[x]==rank[y]) rank[y]++;
        fa[x]=y;
    }
}

这样子就可以开心的解决问题啦

例题 路径压缩

例题 按秩合并