并查集是一种树形数据结构。它管理一系列不相交的集合。它支持两种操作:
- 查询 Find
- 合并 Union
查询
有一个 fa 数组,里面存放了每个节点的父节点。这样下去,查询一个节点的父节点,再查询它的父节点的父节点,再查询它的父节点的父节点的父节点……我们就可以顺藤摸瓜,通过这个数组来查询这个节点的祖先节点。
代码
使用了递归的思想,如果该节点的父节点为它本身说明他就是祖先节点,否则再查询它的父节点。
在这里我在查询的过程中将它的父亲节点设为了它的祖先节点,因为这样下次查询他的时候就可以直接查到祖先节点了,节省一些时间。
inline int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
合并
合并,则将两个集合合并为一个。我们直接将一个集合的祖先的祖先设为另一个集合的祖先即可。
代码
inline int union(int x,int y){
fa[find(x)]=find(y);
}
并查集是一种树形结构,查找与合并的时间复杂度约为 \(O(\log n)\)