并查集

目录

并查集三步走

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

  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

相关文章

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

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

阅读更多
在电脑上安装 Openwrt 作为旁路网关

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

阅读更多
如何在多个编程语言间切换自如

基本思路 基本结构和控制流要记住，也就是熟悉基本语法 识别各自语言的特性，也就是知道高级特性 本文主要是熟悉基本语法，搞清楚不同的编程语言怎么描述相同的功能的。对于高级特性，点到为止。 数据结构 栈 Go stack := make([]string, 0, 10) // 入栈 stack = append(stack, "A") // 出栈 v := stack[len(stack)-1] stack = stack[:len(stack)-1] // 判断是否为空 isEmpty := len(stack) == 0 Python L = [] L.append('D') # 入栈 L.pop() # 出栈 L[-1] # peek 队列 Go queue := make([]int, 0) // 入队 queue = append(queue, 10) // 出队 v := queue[0] queue = queue[1:] // 判断是否为空 isEmpty := len(queue) == 0 Python L = [] L.append('D') # 入队 L.pop(0) # 出队 L[0] # peek 控制流 循环 Go /* Go 只有 for 循环 */ for i, val := range arr { // ... } for i := 0; i < len(arr); i++ { // ... } Python for i in range(10): pass for i in range(0, 10, 1): pass for val in arr: pass for i, val in enumerate(arr): pass else pass while len(queue) > 0: pass else pass while flag: print(str(flag))

阅读更多