并查集

目录

并查集三步走

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

  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;
  }
}

相关文章

在电脑上安装 Openwrt 作为旁路网关

🤔场景 既然回家了,有了家用路由器,就希望各个设备能够不需要安装对应的软件而直接科学上网、屏蔽广告等。 但原来的路由器太小众,没人提供相应的固件,也就是说没法刷机。 后来,我看到有关旁路网关的介绍,觉得这可能是一种解决方案。

阅读更多
内存管理:分段、分区、分页

内存要怎么用起来呢?存储程序的思想,把程序放入内存,程序在CPU中取指执行! 而用户程序有逻辑地址,实际的内存是物理地址,于是先有一个地址重定位的问题。 由于程序载入内存之后,睡眠了的话,还会被移入到磁盘,因此在运行时做重定位更好,这叫做地址翻译。

阅读更多
如何自己本地编译 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 时好时坏。

阅读更多