首页 > 编程语言 >[算法学习笔记] 并查集

[算法学习笔记] 并查集

时间:2024-04-24 23:11:08浏览次数:30  
标签:关系 int 查集 合并 笔记 朋友 算法 敌人

提示:本文并非并查集模板讲解,是在模板基础上的进一步理解以及拓展。

Review

并查集可以用来维护集合问题。例如,已知 \(a,b\) 同属一个集合,\(b,c\) 同属一个集合。那么 \(a,b,c\) 都属一个集合。

并查集分为 合并,查询 操作。定义 \(fa_i\) 表示点 \(i\) 的父亲。为了降低复杂度,在 find 操作向上递归查祖先时我们同步将 \(fa_i\) 更改为 \(i\) 的祖先。这就是所谓路径压缩。

对于合并,为了方便直接合并即可。当然也可以按秩合并优化,虽然我认为优化效果不大。

种类并查集

并查集的传递性非常强大,对于普通的传递关系问题,并查集可以轻松解决。但是,对于有种类关系的,比如"敌人的敌人是朋友” 此类关系又该如何维护呢?

我们来看一到例题。

BOI2003 团伙

Description

现在有 \(n\) 个人,他们之间有两种关系:朋友和敌人。我们知道:

  • 一个人的朋友的朋友是朋友
  • 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

不难发现,本题的关键在于维护 “敌人的敌人是朋友” 这种关系。如果没有这层限制,那本题就是朴素的并查集模板题。

实际上,我们只需要开两倍并查集。对于 \(\forall x,y\) ,若 \(x,y\) 是朋友,合并 \(x,y\) 即可。这是普通并查集操作。反之,若 \(x,y\) 是敌人,分别合并 \(x,y+n\),\(x+n,y\) 即可。这样我们就解决了问题。

接下来我们将通过画图,来解释这样的合并方式是如何工作的。

模拟样例:已知 \(1,2\) 是敌人关系,\(2,4\) 是敌人关系。按照要求,\(1,4\) 应是朋友关系。\(n=4\)
image

不难发现,\(4\) 通过敌人 \(2\) ,\(2\) 与敌人 \(1\) 。\(4\) 与 \(1\) 在同一种类里相连,朋友关系。这就是最简单的种类并查集的工作原理。

这样,我们就解决了本题。

代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int fa[N];
int dist[N];
int ans = 0;
vector <int> Edge;
void Init()
{
	for(int i=1;i<=n*2;i++) 
	{
		fa[i] = i;
		dist[i] = 1;
	}
}
int find(int x)
{
	if(x == fa[x]) return x;
	fa[x] = find(fa[x]);
	return fa[x];
}
void merge(int i,int j)
{
	int x = find(i),y = find(j);
	if(x == y) return;
	if(dist[x] < dist[y]) fa[x] = fa[y];
	else fa[y] = fa[x];
	if(dist[x] == dist[y] && x != y) dist[y] ++; 
}
int main()
{
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	Init();
	for(int i=1;i<=m;i++)
	{
		char op;
		int p,q;
		cin>>op>>p>>q;
		if(op == 'F')
		{
			merge(p,q);
		}
		else 
		{
			merge(p,q+n);
			merge(q,p+n);
		}
	}
	for(int i=1;i<=n;i++)
	{
	//	int f = find(i); 
		if(fa[i] == i) ans ++;
	}
	cout<<ans<<endl;
	return 0;
}

待更。

标签:关系,int,查集,合并,笔记,朋友,算法,敌人
From: https://www.cnblogs.com/SXqwq/p/18156576

相关文章

  • Fast Möbius Transform 学习笔记
    小Tips:在计算机语言中\(\cup\)=&/and,\(\cap\)=|/orFirstStep.定义定义长度为\(2^n\)的序列的and卷积\(A=B*C\)为\(A_i=\sum_{j\cupk=i}{B_j*C_k}\)考虑快速计算SecondStep.变换定义长度为\(2^n\)的序列的Zeta变换为\[\hat{A}_i=\sum......
  • 用一个尽可能高效的算法,查找单向链表(有头结点)中倒数第k个位置上的结点
    思路  定义两个指向链表首结点的指针变量,第一个指针变量向后移动k个位置后,第二个指针变量也开始跟着一起向后移动,直到第一个指针变量指向尾结点为止,第二个指针变量指向的位置结点就是倒数第k个结点。实现步骤及参考代码(C语言)intLList_FindLK(LList_t*Head,DataType_tda......
  • 笔记/C++中的数组排序
    在C++中,std::sort函数是一个用于对容器(如数组、向量等)进行排序的通用算法。它定义在<algorithm>头文件中,并接受两个迭代器参数,分别指向要排序的范围的开始和结束位置。此外,std::sort还可以接受一个可选的比较函数或lambda表达式,用于自定义排序规则。以下是std::sort函数的基本用......
  • SQL学习笔记
    --creattable--auto-generateddefinitioncreatetableemp(idintnullcomment'编号',worknovarchar(10)nullcomment'工号',namevarchar(10)nullcomment'名字',genderchar(1)......
  • 论文笔记-Two-phase flow regime identification based on the liquid-phase velocity
    对象:液相速度信息方法:CNN、LSTM、SVM目标:实现了水平管道内两相流态识别关注特征:从速度时间序列数据中提取的统计特征:均值、均方根和功率谱密度、最大速度比和最大速度差比结果:SVM-93.1%,CNN-94%,LSTM-不佳73.3%LSTM:总共使用了300秒的速度数据,然后将其分为180秒用于训练和......
  • PM 的基本技术训练 – 案例分析 在PM 带领下, 每个团队深入分析下面行业的软件, 找到行
    英语学习/词典App英语学习/词典App评级牛津高阶英汉双解词典app优点:权威的词汇分类,适合专业英语词汇学习,查词功能强大,支持通配符搜索。缺点:可能需要在特定区域的Appstore购买,价格较高。网易有道词典优点:用户评分高,专为iPad设计,提供多种语言翻译,适合学生使用。缺点:可......
  • 2024.4.22(周一)构建之法阅读笔记3
    第六章敏捷流程敏捷开发的原则是:1.尽早并持续地交付有价值的软件以满足顾客需求  2.敏捷流程欢迎需求的变化  3.经常发布可用的软件,发布间隔可以从几周到几个月,能短则短 4.业务人员和开发人员在项目开发过程中应该每天共同工作 5.以有进取心的人为项目核心,充分支持信......
  • 2024.4.18(周四)构建之法阅读笔记1
    第一章概论软件=程序+软件工程  软件企业=软件+商业模式  一个复杂的软件不但要有合理的软件架构、软件设计与实现,还要有各种文件和数据来描述各个程序文件之间的依赖关系、编译参数等等,这些都是软件构建的过程。软件开发的不同阶段:1.玩具阶段 2.业余爱好阶段 3.探索......
  • 2024.4.19(周五)构建之法阅读笔记2
    第四章两人合作在代码规范方面,可以分为两个部分:代码风格规范和代码设计规范。代码风格规范主要是缩进、行宽、括号、断行与空白的{}行、分行、命名、下划线、大小写、注释等;建民老师上课主要强调的是缩进、命名和注释。在代码设计规范方面,主要是函数、goto错误处理、类处理等。......
  • CDQ分治学习笔记
    1.简介CDQ分治是一种思想,类似于动态规划,依照原理和写法的不同,大致分为3类:解决与点对相关的问题1D动态规划的优化及转移通过CDQ分治,将一些动态问题转化为静态问题2.解决与点对相关的问题2.1.流程1.找到序列的中点mid2.将所有的点对(i,j)划分为三类a.\(i\lemi......