“树”据结构：并查集从入门到AC
“树”据结构：并查集
- 前言
- 算法设计
- 代码示例
- 优化
- 相关文章
前言
在一组数据中，数据被分为了不同的集合，那么其中的集合往往可以用树形来表示。而区分集合，与查找集合的元素，就会成为核心的问题。并查集主要就是解决这类问题，因此并查集算法的核心也就是查找与区分。
并查集通过一个一维数组来实现，因此，给我们提供了更大的时间和空间上的便利。通过一维数组来维护一个森林，也就是维护由不同树为子集构成的集合。
问题示例：
有10个学生，1号与2号同班，3号和5号同班，4号和6号同班，7号和3号同班，8号和10号同班，9号和2号同班，8号和4号同班。
然后一般是要求解不同的班级数or输入序号查询同班同学
这类问题都是经典的并查集模板。
算法设计
先动动笔算下我们需要的结果：
1，2，9一个班级
3，5，7一个班级
4，6，8，10一个班级
首先先将一个一维数组初始化，设数组的值为其班级序号，假设每个学生都来自不同的班级，即f[i]=i。
由此f[1]=1,f[2]=2,f[3]=3,…f[10]=10。
然后我们再把结点合并成树，树内部再做处理。
由结点合并为树：以靠左优先进行同班合并，由于输入的条目是1 2，所以2号的2班消失合并到1班
接下来我们要准备的函数是，搜索同班同学的归属，我们先写一个深度搜索：
int dfs(int v)
{
if(a[v]==v)
return v;
else
{
dfs(a[v]);
}
}
于是我们可以搜索到同班同学的最终归属。
而当我们读到输入条目：9号与2号同班的时候，由于2号班级已经消失成为了1号班级（形成了树，而不是单一结点），这时候我们将整个结点归到9号之下：
但这时候我们的算法没有完成，因为在最后的数组下标里，1、2、9明明同属于9班2号学生却属于1班，2向1的指针就多余了，那么我们需要略微处理下搜索算法来处优化冗余数据，也称路径压缩：
如此处理，当最终搜索完成的时候，只要每次存在f[i]=i，就代表了有一个独立的班级，这棵树的最终父节点为i。
代码示例
初始化数据
scanf("%d %d",&n,&m);//输入学生数与数据条目数
for(i=0;i<=n;i++)
{
f[i]=i;//初始化
}
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);//输入每组同班条目
Merge_(x,y);//合并函数
}
合并函数：
进行同班合并
t1与t2代表了v和u的祖先结点，如果t1与t2不相等，t2从下至上一整支需要归并到t1下
void Merge_(int v,int u)
{
int t1=0,t2=0;
t1=getf(v);//查找根部归属
t2=getf(u);
if(t1!=t2)
{
f[t2]=t1;
}
}
搜索函数只需要在上文的基础上稍稍加强一下
int getf(int v)
{
if(f[v]==v)
return v;
else
{
f[v]=getf(f[v]);//路径压缩
return f[v];
}
}
到这里，我们拿上文的题目来做输入输出示例：
有10个学生，1号与2号同班，3号和5号同班，4号和6号同班，7号和3号同班，8号和10号同班，9号和2号同班，8号和4号同班。
求学生来自多少个不同班级
那么用变量 j 来扫描搜索结果：
for(i=1;i<=n;i++)
{
if(f[i]==i)
{
j++;
}
}
得解分为3个班级。
优化
并查集的优化思路不少，但核心都在于，如何高效的来合并树，也就是谁向谁合并。
通俗的说，既然合并的过程是修改被合并的树的祖先认知，由于修改的过程是把树回溯，那么显然，被合并的树越小，速度就会越快，反之越慢。
前文中我们使用的是向左边的树合并，那么现在我们可以始终保持小树向大树合并：
先去声明一个size数组，来表示树的结点数量，并全部初始化为1
void Merge_(int v,int u)
{
int t1=0,t2=0;
t1=getf(v);
t2=getf(u);
if(t1!=t2)
{
if (size[t1] > size[t2]) {//比较大小，然后由小并大
f[t2] = t1;
size[t1] += size[t2];
} else {
f[t1] = t2;
size[t2] += size[t1];
}
}
}
相关文章
二叉树从入门到AC（1）构建和前中后序遍历
二叉树从入门到AC（2）深度与层次遍历
二叉树从入门到AC（3）完全二叉树与堆