并查集模板超详细整理

阳光穿透心脏的1/2处 2021-08-30 01:53 458阅读 0赞

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

·合并（Union）：把两个不相交的集合合并为一个集合。  
·查询（Find）：查询两个元素是否在同一个集合中。

假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组fa\[\]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。

**查询**

int find(int x)
    {
        if(fa[x] == x)
            return x;
        else
            return find(fa[x]);
    }

我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

**合并**

void merge(int i, int j)
    {
        fa[find(i)] = find(j);
    }

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。

**路径压缩**

最简单的并查集效率是比较低的。怎么解决呢？我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步。其实这说来也很好实现。只要我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。这用递归的写法很容易实现：

**合并（路径压缩）**

int find(int x)
    {
        if(x == fa[x])
            return x;
        else{
            fa[x] = find(fa[x]);  //父节点设为根节点
            return fa[x];         //返回父节点
        }
    }

**以上代码常常简写为一行：**

int find(int x)
    {
        return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }

注意赋值运算符=的优先级没有三元运算符?:高，这里要加括号。

**初始化（按秩合并）**

inline void init(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            fa[i] = i;
            rank[i] = 1;
        }
    }

**合并（按秩合并）**

inline void merge(int i, int j)
    {
        int x = find(i), y = find(j);    //先找到两个根节点
        if (rank[x] <= rank[y])
            fa[x] = y;
        else
            fa[y] = x;
        if (rank[x] == rank[y] && x != y)
            rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
    }

**模板整理**

const int maxn = 5005;
    int Fa[maxn],Rank[maxn];
    void init(int n)  ///初始化
    { 
    	for (int i = 1; i <= n; i++)
    	{ 
    		Fa[i] = i;
    		Rank[i] = 1;
    	}
    }
    int find(int x) //查找
    { 
    	return x == Fa[x]? x:(Fa[x] = find(Fa[x]));//路径压缩
    }
     void merge(int i, int j) //合并
    { 
    	 int x = find(i), y = find(j);
    	 if (Rank[x] <= Rank[y])
    	 { 
    		 Fa[x] = y;
    	 }
    	 else
    	 { 
    		 Fa[y] = x;
    	 }
    	 if (Rank[x] == Rank[y] && x!=y)
    	 { 
    		 Rank[y]++;
    	 }
    }

**带权并查集**  
一般的并查集主要记录节点之间的链接关系，而没有其他的具体的信息，仅仅代表某个节点与其父节点之间存在联系，它多用来判断图的连通性，而有的时候在这些边中添加一些额外的信息可以更好的处理需要解决的问题，在每条边中记录额外的信息的并查集就是带权并查集。  
每一条边都记录了每个节点到根节点的一个权值，这个权值该设为什么由具体的问题而定，一般都是两个节点之间的某一种相对的关系。

//查询
    int find(int x)
    { 
    	if (x != Fa[x])
    	{ 
    		int tmp = Fa[x];  //记录父节点
    		Fa[x] = find(Fa[x]);  //将x的父节点设置为根节点
    		value[x] += value[tmp];
    	}
    	return Fa[x];
    }
    //合并
    void merge(int i, int j)
    { 
    	int x = find = (i), y = find(j);
    	if (x != y)
    	{ 
    		Fa[x] = y;
    		value[x] = value[y] + s - value[x];
    	}
    }

参考的文章：链接: [并查集][Link 1].  
链接: [带权并查集][Link 2].  
文章讲的非常详细，不太懂的可以在这里学习。

[Link 1]: https://zhuanlan.zhihu.com/p/93647900/
[Link 2]: https://blog.csdn.net/yjr3426619/article/details/82315133/