并查集
2019-08-18
RT
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题，常常在使用中以森林来表示（一般用数组实现）。
实现核心
1.初始化：
把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。
2.查找
查找元素所在的集合，即根节点。
3.合并
将两个元素所在的集合合并为一个集合。
通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。
代码实现
1.初始化
int f[]; //定义数组f,f[i]表示节点i的父节点
for(int i=1;i<=n;i++) f[i]=i; //n为节点数
2.查找
首先，我们需要引入一个路径压缩的概念。
如果，查找中路径较长（形成一个长长的链），时间复杂度就会比较高。
思想
每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快。
实现
1.找到根结点。
2.修改查找路径上的所有节点，将它们都指向根结点。
int find(int s){ //查找节点s
if(f[s]!=s) f[s]=find(f[s]);
return f[s];
}
3.合并
int u,v; //需要合并的节点u和节点v
int x=find(u);
int y=find(v); //x,y为节点u和节点v的父节点
if（x!=y) f[y]=x; //或f[x]=y;