【并查集】【Union-Find】
admin
2024-05-12 02:21:24
0

Union-Find算法

  • 基本概念
    • 并查集模板
      • 1. [参考leetcode](https://leetcode.cn/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/)
      • 2.平衡优化和重量优化

基本概念

  • 并查集是一种数据结构
  • 并查集这三个字,一个字代表一个意思。
    并(Union),代表合并
    查(Find),代表查找
    集(Set),代表这是一个以字典为基础的数据结构,它的基本功能是合并集合中的元素,查找集合中的元素
  • 并查集的典型应用是有关连通分量的问题
  • 并查集解决单个问题(添加,合并,查找)的时间复杂度都是O(1)
  • 因此,并查集可以应用到在线算法中

链接:https://leetcode.cn/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/

并查集模板

1. 参考leetcode

class UnionFind{
public:// 查找祖先:如果节点的父节点不为空,那就不断迭代。int find(int x){int root = x;while(father[root] != -1){root = father[root];}// 路径压缩while(x != root){int original_father = father[x];father[x] = root;x = original_father;}return root;}// 判断两个节点的连通性bool is_connected(int x,int y){return find(x) == find(y);}// 合并两个节点:如果发现两个节点是连通的,// 那么就要把他们合并,也就是他们的祖先是相同的。// 这里究竟把谁当做父节点一般是没有区别的。void Union(int x,int y){int root_x = find(x);int root_y = find(y);if(root_x != root_y){father[root_x] = root_y;num_of_sets--;}}// 初始化:当把一个新节点添加到并查集中,它的父节点应该为空void add(int x){if(!father.count(x)){father[x] = -1;num_of_sets++;}}int get_num_of_sets(){return num_of_sets;}private:// 记录父节点unordered_map father;// 记录集合数量int num_of_sets = 0;
};

2.平衡优化和重量优化

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作: 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统(六):学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤: 在Student.cpp的...
JAVA多线程知识整理 Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP... [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍 低功耗通用异步接收器(LPUART) 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振... 城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段࿰...
程序的循环结构和random库...   第三个参数就是步长     引入文件时记得指明字符格式,否则读入不了 ...
中国版ChatGPT在哪些方面... 目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu... 2023 年 1 月 25 日,Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis... Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比... 文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法 1. 前缀和 假设有一个数组,我们想大量频繁的去访问L到R这个区间的和,...
windows安装JDK步骤 一、 下载JDK安装包 下载地址:https://www.oracle.com/jav...
分治法实现合并排序(归并排序)... 🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨...
在linux上安装配置node... 目录前言1,关于nodejs2,配置环境变量3,总结 前言...
Linux学习之端口、网络协议... 端口:设备与外界通讯交流的出口 网络协议:   网络协议是指计算机通信网...
Linux内核进程管理并发同步... 并发同步并发 是指在某一时间段内能够处理多个任务的能力,而 并行 是指同一时间能够处理...
opencv学习-HOG LO... 目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义 导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu... 写在前面 前期积累: GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...