许久未更新今天小小的学习一下

让我开始我们的学习之旅

 并查集

引入

首先我们引入一个概念,并查集是管理元素所属集合的数据结构,可以理解为一个集合 一棵树---这一颗树的每个节点都是一个元素。

比如图中的元素1 ,2, 3, 4, 5 属于一个集合, 元素6, 7, 8属于一个集合 并查集就是实现所管元素的数据结构

支持操作

并查集支持两个操作 合并(merge)与查询(find)

1-合并: 合并两个元素的集合

2-查询: 查询所属元素所在的集合,也可以查询两个元素是否相同

代码实现 

1-初始化

对于单独的一个元素来讲,它的父亲就是它自己,为了实现这个操作我们需要初始化,将每一个元素都定义为的父亲自己

void init() {
    for (int i = 0; i <= N; i++) {
        fa[i] = i;
    }
}