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

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

算法流程

初始化

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

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

查找

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

合并

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

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

模板代码

基础模板

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。

void move(int a)
{
    int p = find_set(id[a]);
    cnt[p]--;
    sum[p] -= a;         //消除该位置的点在原来集合中的影响
    id[a] = ++dex;       //开辟新的位置表示这个编号的点
    parent[dex] = dex;
    cnt[dex] = 1;
    sum[dex] = a;
}

相关题目

• HDU - 1232 畅通工程（简单并查集）
• HDU - 1272 小希的迷宫（简单并查集）要判断是否出现环
• POJ - 2524 Ubiquitous Religions（简单并查集）求连通分量
• POJ - 1308 Is It A Tree?（简单并查集）判断是否出现环
• POJ - 1611 The Suspects （简单并查集）求0所在集合有多少元素
• POJ - 2236 Wireless Network （简单并查集）判断元素是否在同一个集合中
• HDU - 2545 树上战争 （没有压缩路径的并查集）查询节点到根节点的步数
• UVA - 11987 Almost Union-Find（带删除的并查集）消除原来位置的影响，开辟新位置表示
• POJ - 1182 食物链（种类并查集经典）注意关系域的更新，利用向量加减得出转移公式
• POJ - 1703 Find them, Catch them （种类并查集）与上一题类似
• POJ - 2492 A Bug's Life（种类并查集）
• POJ - 1988 Cube Stacking （带权并查集）
• POJ - 1962 Corporative Network（带权并查集）