首页 > 编程语言 >(来一套)JavaScript并查集模板

(来一套)JavaScript并查集模板

时间:2023-12-11 14:22:07浏览次数:47  
标签:cnt JavaScript return parent 查集 findset 模板 size

code: 

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.size = new Array(n).fill(1);
        this.cnt = n;
    }

    findset(x) {
        if (this.parent[x] === x) {
            return x;
        }
        this.parent[x] = this.findset(this.parent[x]);
        return this.parent[x];
    }

    unite(a, b) {
        let x = this.findset(a);
        let y = this.findset(b);
        if (x === y) {
            return false;
        }
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        this.parent[y] = x;
        this.size[x] += this.size[y];
        this.cnt -= 1;
        return true;
    }

    connected(a, b) {
        const x = this.findset(a);
        const y = this.findset(b);
        return x === y;
    }
}

 

标签:cnt,JavaScript,return,parent,查集,findset,模板,size
From: https://www.cnblogs.com/fanqshun/p/17894303.html

相关文章

  • 第五十八天 网页伪静态,视图层,模板层
    内容概要网页伪静态视图层1.三板斧2.JsonResponse3.form表单上传文件4.FBV与CBV(核心)5.CBV源码(面向对象)模板层1.模板语法传值2.模板语法之过滤器3.模板语法之标签4.自定义过滤器、标签、inclusion_tag一、网页伪静态将动态网页伪装成静态网页从而提升网页被......
  • 我用 AI 写的《JavaScript 工程师的 Python 指南》电子书发布啦!
    关于本书你好,我是luckrnx09,一名靠React恰饭的前端工程师,很高兴向你介绍我的第一本开源电子书《JavaScript工程师的Python指南》。本书的内容完全免费,开源地址:https://github.com/luckrnx09/python-guide-for-javascript-engineers为什么会有这本书2022年,ChatGPT引起了......
  • Js(Javascript)中的apply方法的使用
    ​ JavaScript中的apply()方法用于调用函数,允许指定函数的this对象和参数。也就是通过function的apply方法来调用方法,可以改变方法的this的对象,并且还可以传入方法参数,apply对于面向对象编程还是很有用的。参考文档:Js(Javascript)中的apply方法的使用-CJavaPy1、基本语......
  • 常量与变量:JavaScript中的稳定与灵活
    在编程的世界里,数据的存储与操作是构建任何功能的基础。在JavaScript这门轻量级,解释型的脚本语言中,处理数据的两个基本概念是常量(Constants)和变量(Variables)。理解它们的区别与用法,对于编写高效、可维护的代码至关重要。变量:数据的灵活容器在JavaScript中,变量可以被视为数据的容器。......
  • 算法竞赛模板整理
    图论最短路structSPFA{vector<i64>dis;vector<bool>vis;vector<int>from;intn;SPFA(vector<vector<pair<int,i64>>>&g,ints):n(g.size()){dis.assign(n,INF),vis.assign(n,false),f......
  • 线段树模板区间加(含懒标记)
    constintN=1e5+10;intn,m;inta[N];structTree{ intl,r; llsum,add; }tr[4*N];voidbuild(intu,intl,intr){ //l=tr[u].l;r=tr[u].r; //注释掉的部分是典型的错误,对于build过程中我们是初始化编号对应区间节点,上面赋值逻辑反了 tr[u]={l,r}; if(l==r)t......
  • 带权并查集
    对于种类并查集主要是考虑清楚到根节点距离分为几类,每一类的意义有的题目相出d数组的含义才能想到用带权并查集//find函数需要变化intfind(intx){if(p[x]!=x){introot=find(p[x]);d[x]+=d[p[x]];p[x]=root;}retur......
  • JavaScript 学习
    变量声明和数据类型varname='John';letage=25;constPI=3.14;//数据类型:字符串、数字、布尔值//var声明(ES5),let和const声明(ES6)var、let和const是JavaScript中声明变量的关键字。var在ES5中使用,let和const在ES6中引入,具有块级作用域,能避免变量提升的问题......
  • Spring Boot学习随笔- 集成JSP模板(配置视图解析器)、整合Mybatis(@MapperScan注解的使用
    学习视频:【编程不良人】2021年SpringBoot最新最全教程第五章、JSP模板集成5.1引入JSP依赖<!--引入jsp解析依赖--><!--C标签库--><dependency><groupId>jstl</groupId><artifactId>jstl</artifactId><version>1.2</version></depen......
  • JavaScript-history对象
    概述window.history属性指向History对象,它表示当前窗口的浏览历史。History对象保存了当前窗口访问过的所有页面网址。下面代码表示当前窗口一共访问过3个网址。window.history.length//3由于安全原因,浏览器不允许脚本读取这些地址,但是允许在地址之间导航。//后退到前一个网......