并查集

目录

并查集三步走

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

  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 界面那么一定会好很多,一个下拉列表就可以解决 有没有解决方案,不需要自己造轮子的那种?

阅读更多
如何在 React 中进行状态管理?使用 Zustand!

计数器 import { create } from 'zustand' const useStore = create(set => ({ count: 1, inc: () => set(state => ({ count: state.count + 1 })), })) function Controls() { const inc = useStore(state => state.inc) return <button onClick={inc}>one up</button> } function Counter() { const count = useStore(state => state.count) return <h1>{count}</h1> } 用法 创建状态 state 操作 action Basic typescript usage doesn’t require anything special except for writing create<State>()(...) instead of create(...)… import { create } from 'zustand' interface BearState { bears: number increase: (by: number) => void } const useBearStore = create<BearState>()((set) => ({ bears: 0, increase: (by) => set((state) => ({ bears: state.bears + by })), })) const useFishStore = create((set) => ({ salmon: 1, tuna: 2, deleteEverything: () => set({}, true), // clears the entire store, actions included deleteTuna: () => set((state) => omit(state, ['tuna']), true), })) const useSoundStore = create((set, get) => ({ sound: "grunt", action: () => { const sound = get().sound // you still have access to state outside of it through get // ... } }) export default useBearStore 在 react 之外使用呢?

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

基本思路 基本结构和控制流要记住,也就是熟悉基本语法 识别各自语言的特性,也就是知道高级特性 本文主要是熟悉基本语法,搞清楚不同的编程语言怎么描述相同的功能的。对于高级特性,点到为止。 语法简介 语法特性 Python Go 变量声明 动态类型,无需声明 静态类型,必须声明 代码块 缩进(空格/制表符) {} 包裹 循环 for、while 只有 for 函数 def,支持默认参数 func,无默认参数 错误处理 try-except 返回 error + if err != nil 并发 threading(GIL 限制) goroutine + channel 面向对象 完整类继承 struct + interface 包管理 pip + import go mod + import 内置函数 Python 的内置函数更丰富,适合快速开发;Go 的内置函数较少,但更专注于底层控制和性能优化。

阅读更多