【常用模板】并查集
浏览 188 | 评论 0 | 字数 1528
TTQ
2021年01月01日
  • 并查集是一种树形的数据结构,顾名思义,它用于处理一些不交集的合并查询问题。 它支持两种操作:

    • 查找(Find):确定某个元素处于哪个子集;
    • 合并(Union):将两个子集合并成一个集合。

    初始化

    首先,在并查集初始化时,我们认为每一个元素都构成一个独立的子集,故每一个元素的父亲都是自己。

    void makeSet(int size) 
    {
      for (int i = 0; i < size; i++) fa[i] = i;  // i就在它本身的集合里
      return;
    }

    查找

    每一个元素都能知道自己的父亲(上一级)是哪一个元素,如果再向父级查找父级,一直到一个父级为自身的元素时,就代表找到了祖先,那么就实现了并查集的查找算法。

    int fa[MAXN];  // 记录某个人的爸爸是谁,特别规定,祖先的爸爸是他自己
    int find(int x) 
    {
      // 寻找x的祖先
      if (fa[x] == x)  // 如果x是祖先则返回
        return x;
      else
        return find(fa[x]);  // 如果不是则x的爸爸问x的爷爷
    }

    路径压缩

    有了查找算法,我们就可以让所有的元素直接指向自己的祖先,而省去一层层询问的时间,对于新加入的元素,也只需要一次询问即可找到其祖先。

    int find(int x) 
    {
      if (x != fa[x])  // x不是自身的父亲,即x不是该集合的根
        fa[x] = find(fa[x]);  // 查找x的祖先直到找到根,于是顺手路径压缩
      return fa[x];
    }

    合并

    如果出现两个独立的子集需要进行合并,使其中一个成为另一个的父亲,那么就需要进行合并,从上文可以知道,只需把其中一个祖先变成另一个祖先的儿子即可。

    void join(int x, int y) 
    {
      // x 与 y 所在家族合并
      x = find(x);
      y = find(y);
      fa[x] = y;  // 把 x 的祖先变成 y 的祖先的儿子
    }

    完整代码

    int fa[MAXN];
    
    int find(int x)
    {
      if (x != fa[x])
        fa[x] = find(fa[x]);
      return fa[x];
    }
    
    void makeSet(int size)
    {
      for (int i = 0; i < size; i++) fa[i] = i;
      return;
    }
    
    void join(int x, int y) 
    {
      x = find(x);
      y = find(y);
      fa[x] = y;
    }

    接口

    fa数组用于存储某个元素的祖先是谁,find函数用于寻找元素祖先并进行路径压缩,makeSet函数用于初始化,join函数用于合并新元素。

    本文作者:TTQ
    本文链接:https://ponder.fun/archives/79.html
    最后修改时间:2021-01-01 16:50:00
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论