并查集

目录

并查集三步走

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

  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

相关文章

JWT 的应用场景思考

JWT 的应用场景思考 简述 JWT JWT,全称 JSON Web Token。是一种开放标准,用于在各方之间安全传递信息,它是以 Base64 编码 json 对象的 token 。基于 token 的权限验证,与传统的 Session 认证完全不同,它不需要服务端保持 Session 记录,连用户状态都不需要关心。一旦用户登录网站,服务器就会生成 token,之后客户端每次登录时在HTTP的头信息中带上 token 即可。

阅读更多
搭建起本地的 DevOps 环境

动机 自己作为独立开发者,也想体验那种写完代码效果就出来的感觉,不用又当个运维人员。 想当初 Spring Boot 程序,得手动编译,然后手动复制到目标机器,然后重启服务,可麻烦了。 因此,本地跑一套 DevOps 或者 GitOps 的系统应该会很有趣。 方案 整体方案就是通过 CNCF 等的开源软件。

阅读更多
Neo4j: 图数据基本概念、语法与增删改查

Neo4j 简介 Neo4j 使用属性图(Property Graph)模型1。 一个图包含节点(Objects)和边(Relationships)。 Neo4j 的属性图模型包含了: 节点 节点标签:用于区分节点的类型,0个或多个 边:源节点与目标节点之间的一条有向边 边类型:用于区分边的类型,有且仅有1个 属性:节点和边都可以有属性(键值对)用于描述节点和边 注意这些名词的英文:node、relationship、label(节点可以有0个或多个标签)、type(边只有一个类型)、property

阅读更多