首页 > 其他分享 >并查集学习笔记

并查集学习笔记

时间:2023-11-20 18:12:34浏览次数:37  
标签:元素 int 查集 笔记 学习 fa 祖先 find

简介

这里引用OI-wiki上的内容:

并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。
顾名思义,并查集支持两种操作:
合并(Union):合并两个元素所属集合(合并对应的树)
查询(Find):查询某个元素所属集合(查询对应的树的根节点),这可以用于判断两个元素是否属于同一集合

看不懂?

简单来说,并查集就是一种简单的判断两个元素是否在同一个集合中,或者说,有相同的“祖先”。并查集支持查讯,合并等操作。

并查集的基本逻辑可以做个类比:拜师!假设有两个习武之人要比拼比拼,可能在现实生活中他们会打一打,但是在并查集的逻辑中,他们是叫他们的师傅(也就是术语中的“祖先”)来比拼一番。输了的那一方将会带着这一派整个加入到另一个老师傅的帮派中。

示范代码

并查集模板题

首先,我们要有一个用来记录每个元素祖先的数组fa,在一开始,每个元素的祖先就是它本身,于是我们可以写出代码:

void init(){ // 本人习惯用函数来初始化
    for (int i = 1; i <= n; i++) fa[i] = i;
    return ;
}

但是题目的要求不止这些,我们先来实现查询每个元素的祖先。我们可以知道,如果一个元素没有被合并,那么它的祖先一定是自己。那么我们可以不断查找某个元素的直接祖先是谁,再查找那个元素的祖先,直到那个元素的祖先是它本身为止。

同时为了优化,我们可以在查找的过程中将中途所经历的元素的祖先直接设为最后的祖先,也就是修为高深的老师傅。因为总体来说这些元素仍处于最终的祖先的管理之下,所以不会导致混乱:

int find(int x){
    if (fa[x] == x) return x; // 找到了祖先
    return fa[x] = find(fa[x]);
}

或者用三元运算符的形式:

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

并查集的合并操作,说难也不难,就是修改每个元素在fa数组里的值即可,那么我们可以写出以下代码:

void merge(int x, int y){
    int fx = find(x), fy = find(y); // 查找两个元素的祖先
    if (fx == fy) return ; // 在同一个集合中就跳过
    fa[fx] = fy;
    return ;
}

那么最终可以写出代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, fa[10005];

void init(){
    for (int i = 1; i <= n; i++) fa[i] = i;
    return ;
}

int find(int x){
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}

void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy;
    return ;
}

int main(){
    cin >> n >> m;
    init();
    int z, x, y;
    for (int i = 0; i < m; i++){
        cin >> z >> x >> y;
        if (z == 1) merge(x, y);
        else{
            if (find(x) == find(y)) cout << "Y" << endl;
            else cout << "N" << endl;
        }
    }
    return 0;
}

练习题:

带权并查集

我们可以在并查集的边上定义某种权值(比如大小,长度等)来解决更多的问题。

来看P1196 [NOI2002] 银河英雄传说这道题。在这道题中,我们要实现合并和查询两种操作。我们可以想到维护每个舰队的长度,但为了更精确的描述两艘战舰之间的距离,我们还要维护每艘战舰到队列头部的距离。所以我们不难写出以下代码:

#include <bits/stdc++.h>
using namespace std;

int t, fa[30005], a, b, l[30005], front[30005];
char op;

int find(int x){
	if (fa[x] == x) return x;
	int k = fa[x]; // 要先保存下来父节点
	fa[x] = find(fa[x]);
	front[x] += front[k]; // 更新当前战舰到队列头部的距离
	l[x] = l[fa[x]]; // 更新队列长度
	return fa[x];
}

int main(){
	cin >> t;
	for (int i = 1; i <= 30000; i++){
		fa[i] = i;
		l[i] = 1;
		front[i] = 0;
	}
	while(t--){
		cin >> op >> a >> b;
		if (op == 'M'){
			int x = find(a), y = find(b);
			if (x == y) continue;
			fa[x] = y; // 进行合并操作
			front[x] += l[y]; // 修改原来队列头部的战舰到新的队列头部的距离
			l[x] += l[y]; // 更新队列长度
			l[y] = l[x];
		}
		else{
			int x = find(a), y = find(b);
			if (x != y) cout << -1 << endl;
			else cout << abs(front[a] - front[b]) - 1<< endl;
		}
	}
	return 0;
}

练习题:

种类并查集

种类并查集适用于拥有对称关系的题目,比如敌人的敌人是朋友之类的。解决这种问题,我们一般会把这种关系所指代的对象建立一个虚拟的节点,然后再把满足这个关系的节点与这个虚拟节点进行合并。

比如P1892 [BOI2003] 团伙这道题,我们可以对每个人的敌人建立一个虚拟节点,然后将具有敌对关系的人与虚拟节点进行合并即可。不难写出这样的代码:

#include <bits/stdc++.h>
using namespace std;

int n, fa[2010], m, p, q;
char opt;

void init(){
	for (int i = 1; i <= n * 2; i++) fa[i] = i; // 注意初始化节点的规模要扩大一倍
	return ;
}

int find(int x){
	if (x == fa[x]) return fa[x];
	return fa[x] = find(fa[x]);
}

void merge(int x, int y){
	if (find(x) == find(y)) return ;
	fa[find(x)] = find(y);
	return ;
}

int main(){
	cin >> n >> m;
	init();
	for (int i = 1; i <= m; i++){
		cin >> opt >> p >> q;
		if (opt == 'F'){
			merge(p, q);
		}
		else{// 节点i的敌人为i + n
			merge(q + n, p);
			merge(p + n, q);
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) if (fa[i] == i) cnt++;
	cout << cnt;
	return 0;
}

练习题:

标签:元素,int,查集,笔记,学习,fa,祖先,find
From: https://www.cnblogs.com/Floze3/p/17844527.html

相关文章

  • 学习随笔(设计模式:建造者模式)
    内容今天学习了建造者模式。1.建造者模式是将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。2.简单来说就是一个类的所有的特性方法与这个类对象的构建分离3.本来觉得有点类似于工厂模式,但细想又不太一样。工厂模式是创建一个类,这个类用来创新用户......
  • 学习指南:如何快速上手媒体生态一致体验开发
    过去开发者们在使用多媒体能力时,往往会遇到这样的问题,比如:为什么我开发的相机不如系统相机的效果好?为什么我的应用和其他的音乐一起发声了,我要怎么处理?以及我应该怎么做才能在系统的播控中心里可以看到呢?对于开发者的这些疑问,HarmonyOS通过提供简单易用体验一致的生态接口,使得开发......
  • 大学物理下笔记
    电荷和场关键方程说明方程Coulomb'slaw库仑定律\(\vec{\mathbf{F}}_{12}=\dfrac{1}{4\pi\varepsilon_0}\dfrac{q_1q_2}{r_{12}^2}\hat{\mathbf{r}}_{12}\)无限导线的电场\(\vec{\mathbf{E}}(z)=\dfrac{1}{4\pi\varepsilon_0}\dfrac{2\lambda}{z}\hat{\m......
  • 一 Linux 学习
    远程登录一台linux后,怎么查看是什么发行版。一般来说 Linux著名系统分两大类  Redhat系列:Redhat centosfedora  Debian系列:DebianUbuntu   1.有yum命令的是Redhat系列,有apt-get是Debian系列  2.使用lsb_release-a 命令。        可......
  • 秦疆的Java课程笔记:33 流程控制 Scanner
    之前学习的基本语法中并没有实现程序和人的交互,但是Java给我们提供了这样一个工具类,可以获取用户的输入。java.util.Scanner是Java5的新特性,可以通过Scanner类来获取用户的输入。基本语法:Scanners=newScanner(System.in);通过Scanner类的nexr()与nextLine()方法获取输入的......
  • 第十三章学习笔记
    第十三章学习笔记摘要本章论述了TCP/IP和网络编程,分为两个部分。第一部分论述了TCP/IP协议及其应用,具体包括TCP/IP栈、IP地址、主机名、DNS、IP数据包和路由器;介绍了TCP/P网络中的UDP和TCP协议、端口号和数据流;阐述了服务器-客户机计算模型和套接字编程接口;通过使用UDP和TC......
  • ObjectScript 语法学习一
    简介ObjectScript是一种对象编程语言,专为在InterSystemsIRIS®上快速开发复杂的业务应用程序而设计.作用ObjectScript源代码被编译为在InterSystemsIRIS虚拟机内执行的目标代码。该目标代码针对业务应用程序中常见的操作进行了高度优化,包括字符串操作和数据库访问。......
  • JVM深入学习-ClassLoader篇(一)
    初识JVM---ClassLoader深入理解ClassLoader、SPI机制Class对象的理解java在诞生之初,就有一次编译到处运行的名言,今天我们来探究一下,从java代码到class到运行,JVM中的ClassLoader充当一个什么样的角色。一个简单的JVM流程图(简单了解)流程图.jpg从位置角度理解JVM:就JVM在......
  • 信息安全系统设计与实现课程第十三章学习笔记
    一、知识点归纳1网络编程简介TCP/IP协议、UDP和TCP协议、服务器-客户机计算、HTTP和Web页面、动态Web页面的PHP和CGI编程2TCP/IP协议IPv432位地址IPv6128位地址TCP/IP协议顶层是使用TCP/IP的应用程序,用于登录到远程主机的ssh,用于交换电子邮件的mail、用于Web页面的ht......
  • rsync命令学习
    一、命令介绍sync命令:刷新文件系统缓存,强制将修改过的数据块写入磁盘async命令:将数据先缓存在缓冲区,再周期性同步到磁盘,性能较好,但是数据容易丢失rsync:远程同步rsync命令的特点:1.可以保留原有文件权限,文件属组属主,时间链接文件,文件属性等信息2.传输效率高,只比较变化的数据3......