“树”据结构：并查集从入门到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）完全二叉树与堆