查并集算法
2021-08-02 09:42:38 0 举报
AI智能生成
查并集
作者其他创作
大纲/内容
并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:
合并(Union):把两个不相交的集合合并为一个集合。
查询(Find):查询两个元素是否在同一个集合中。
并查集的重要思想在于,用集合中的一个元素代表集合。
合并(Union):把两个不相交的集合合并为一个集合。
查询(Find):查询两个元素是否在同一个集合中。
并查集的重要思想在于,用集合中的一个元素代表集合。
并查集理解比喻
把集合比喻成帮派,而代表元素则是帮主。接下来我们利用这个比喻,看看并查集是如何运作的。
1. 所有大侠一开始各自为战。他们各自的帮主自然就是自己。
(对于只有一个元素的集合,代表元素自然是唯一的那个元素)
(对于只有一个元素的集合,代表元素自然是唯一的那个元素)
2. 现在1号和3号比武,假设1号赢了(这里具体谁赢暂时不重要),那么3号就认1号作帮主
(合并1号和3号所在的集合,1号为代表元素)。
(合并1号和3号所在的集合,1号为代表元素)。
3. 现在2号想和3号比武(合并3号和2号所在的集合),但3号表示,别跟我打,让我帮主来收拾你(合并代表元素)。
不妨设这次又是1号赢了,那么2号也认1号做帮主。
不妨设这次又是1号赢了,那么2号也认1号做帮主。
4. 现在我们假设4、5、6号也进行了一番帮派合并,江湖局势变成下面这样:
5. 现在假设2号想与6号比,跟刚刚说的一样,喊帮主1号和4号出来打一架(帮主真辛苦啊)。
1号胜利后,4号认1号为帮主,当然他的手下也都是跟着投降了。
1号胜利后,4号认1号为帮主,当然他的手下也都是跟着投降了。
6. 经过不断合并得到一个树状的结构,要寻找集合的代表元素,只需要一层一层往上访问父节点,直达树的根节点
并查集实现
初始化
int fa[MAXN];
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
fa[i] = i;
}
假如有编号为1, 2, 3, ..., n的n个元素,我们用一个数组fa[]来存储每个元素的父节点(因为每个元素有且只有一个父节点,所以这是可行的)。
一开始,我们先将它们的父节点设为自己。
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
fa[i] = i;
}
假如有编号为1, 2, 3, ..., n的n个元素,我们用一个数组fa[]来存储每个元素的父节点(因为每个元素有且只有一个父节点,所以这是可行的)。
一开始,我们先将它们的父节点设为自己。
查询
int find(int x)
{
if(fa[x] == x)
return x;
else
return find(fa[x]);
}
我们用递归的写法实现对代表元素的查询:一层一层访问父节点,直至根节点(根节点的标志就是父节点是本身)。
要判断两个元素是否属于同一个集合,只需要看它们的根节点是否相同即可。
{
if(fa[x] == x)
return x;
else
return find(fa[x]);
}
我们用递归的写法实现对代表元素的查询:一层一层访问父节点,直至根节点(根节点的标志就是父节点是本身)。
要判断两个元素是否属于同一个集合,只需要看它们的根节点是否相同即可。
合并
inline void merge(int i, int j)
{
fa[find(i)] = find(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]; //返回父节点
}
}
把沿途的每个节点的父节点都设为根节点
{
if(x == fa[x])
return x;
else{
fa[x] = find(fa[x]); //父节点设为根节点
return fa[x]; //返回父节点
}
}
把沿途的每个节点的父节点都设为根节点
按秩合并
例如我们需要合并集合7和集合8
设置谁为帮主是会影响树深度的
初始化
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
rank[i] = 1;
}
}
我们用一个数组rank[]记录每个根节点对应的树的深度(如果不是根节点,其rank相当于以它作为根节点的子树的深度)。一开始,把所有元素的rank(秩)设为1。
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
rank[i] = 1;
}
}
我们用一个数组rank[]记录每个根节点对应的树的深度(如果不是根节点,其rank相当于以它作为根节点的子树的深度)。一开始,把所有元素的rank(秩)设为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
}
合并时比较两个根节点,把rank较小者往较大者上合并。
{
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
}
合并时比较两个根节点,把rank较小者往较大者上合并。
0 条评论
下一页