并查集

目录

并查集三步走

并查集,开始的时候大家都是孤岛,根节点就是自己,然后我们不断地合并、修改指针,直到所有边都访问到。

  1. 数组初始化,每个节点的 parent 指针都指向自己。数组 roots 存放所有节点的祖先节点(根节点,路径压缩)【如果要求子集中元素数量,那么还要再创建一个 counts 数组,存储一份子集元素中的数量,需要在 union 中更新】。
  2. 根据所有相连的边,不断地进行查找、合并。
  3. 查找用递归、同时能修改查找路径上的所有节点的 parent 指针,合并前先调用查找然后看是否同一子图,是则合并失败,不是则直接将 parent 指针修改一下即可。

**有向图是否有环?**拓扑排序 DAG !

**无向图是否有环?**并查集!

关于求子集的个数、子集中元素的个数,可以试试把问题转化为图的问题,那么就可以转化为子图的数目、子图中元素数目,应用图的搜索、并查集等!

Java 代码

public class UFC {
  
  private int[] roots;
  
  public UFC(int n) {
    // 并查集用数组存parent
    roots = new int[n];
    // 开始时都是孤岛,根节点的parent都指向自己
    for (int i = 0; i < n; i++) {
      roots[i] = i;
    }
  }
  
  // find 查找是递归
  public int findRoot(int i) {
    // 根节点一定指向自己
    if (roots[i] == i) return i;
    roots[i] = findRoot(roots[i]);
    return roots[i];
  }
  
  // union 合并改指针
  public boolean union(int i, int j) {
    int rootI = findRoot(i);
    int rootJ = findRoot(j);
    if (rootI == rootJ) return false;
    // 把根节点的parent指针直接更改
    roots[rootI] = rootJ; 
    return true;
  }
}
comments powered by Disqus

相关文章

beancount-gs 一款 self-hosted 复式记账程序,简化你的记账方式!

本程序将部署在 macOS 上,不使用 Docker(mac 上的 Docker 太卡了) 动机 我利用 beancount 来记账已经有一段时间了,但有些痛点问题困扰着我: 没有 web 界面,fava 真的只能用来展示和分析且不好理解,需要有一个方便记账的界面 text 记账的方式,在 vscode 插件能力有限的情况下,很容易忘记 assets 和 expenses 到底叫啥名,如果有 web 界面那么一定会好很多,一个下拉列表就可以解决 有没有解决方案,不需要自己造轮子的那种?

阅读更多
如何自己本地编译 OpenWrt ?

感觉不如直接下载,然后用转换工具把 img 搞成 vmfs,见linux - VMware安装OpenWrt,工具下载链接https://www.starwindsoftware.com/tmplink/starwindconverter.exe。 关于系统 LEAN 的不行,还是 ImmortalWrt 更好!还可直接下载 vmfs,注意系统日志等级它默认的 debug 可不行。 关于上网控制插件,注意会和广告过滤 ACC 加速等冲突,有舍有得啊,openwrt上网时间控制为什么设置后无效-OPENWRT专版-恩山无线论坛 (right.com.cn)。 老老实实用 clash for windows 了,OpenWrt 很不稳定啊,github 时好时坏。

阅读更多
单调栈

陈述 顾名思义,就是单调的栈,可严格可不严格。能够找到下一个更大/小的元素,同时能找到上一个大于等于/小于等于的元素。 通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了1。

阅读更多