16.并查集.md

并查集

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

概念

并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

基本操作

• 1.初始化（init）
• 2.查询（Find）: 确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集
• 3.合并（Union）: 将两个子集合并成同一个集合

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于创建单元素集合。有了这些方法，许多经典的划分问题可以被解决。

初始化

我们用 par 数组表示i结点的父亲，rank数组表示树的高度，当par[x] = x 时，x就是所在树的根，因为刚开始没有边，每个结点就是自己的根。

void init(int n)
{
    for(int i = 0; i < n; i++)
    {
        par[i] = i;
        rank[i] = 0;
    }
}

查询

写法1（递归）

int find( int x)
{
    if(par[x] == x)
        return x;
    else
        return par[x] = find( par[x]);//路径压缩
}

写法2

int find(int x)
{
    int root, temp;
    root = x;
    while(root != par[root])//查找位置
        root = par[root];
    while(x != root)//路径压缩
    {
        temp = par[x];
        par[temp] = root;
        x = temp;
    }
    return root;
}

合并

void union(int x,int y)//合并x,y所在集合
{
    x = find(x);
    y = find(y);
    if(x == y)//判断x,y是否属于同一集合
        return ;
    //防止树退化（辉哥说用了很多年从来发现有明显优化的现象发生。。。）
    if(rank[x] < rank[y])
        par[x] = y;
    else
    { 
        par[y] = x;
        if(rank[x] == rank[y])
            rank[x]++;
    }
}

学习视频

并查集讲解