重拾算法-3.2-图论-并查集

为什么会突然想起要重拾算法呢？上次认真的学习、复习算法已经是3年以前了，那时候是为了校招，在这之后算法似乎变的不太重要。我只是矜矜业业地做好前端开发该做的工作，但在业务开发越来越熟练的时候，我发现自己的视野也会变的越来越窄。做程序开发，广度和深度是同样重要的，也许现在的工作中不会直接用上，但是算法、设计模式等等这些底层的知识时候熟练掌握，是我们能不能走得更远的前提，我觉得是时候，再重拾起已经快遗忘的算法，为自己的下一个三年，储备更多的基础知识。作为前端开发，本系列的算法代码实现，将全部用TypeScript实现，同时也会贴一些力扣的题目方便上手实践。

算法流程

初始化

把每个点所在集合初始化为其自身。（有另一种初始化为-1）

通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。

查找

查找元素所在的集合，即根节点。

合并

将两个元素所在的集合合并为一个集合。

通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

模板代码

基础模板

代码语言：javascript复制

void make_set()
{
    for (int i = 0; i <= n; i  )
        parent[i] = -1;
}

int find_set(int t)
{
    if (parent[t] == -1)
        return t;
    else
        return parent[t]=find_set(parent[t]);
}

void union_set(int a, int b)
{
    int t1 = find_set(a);
    int t2 = find_set(b);
    if (t1 != t2)
        parent[t2] = t1;
}

带删除的并查集

思路：消除节点在原来集合中的影响，开辟新位置表示该编号的节点，id表示编号的真实位置，合并、查找的参数都是id。