并查集拓展(扩展域并查集)

        事实证明,扩展域并查集应该在带权并查集前面讲的,因为比较好理解,而且回过头看带权并查集可能也会更轻松一些。

https://www.luogu.com.cn/problem/P1892icon-default.png?t=N7T8https://www.luogu.com.cn/problem/P1892

题目描述

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

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

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

输入格式

第一行输入一个整数 𝑛 代表人数。

第二行输入一个整数 𝑚 表示接下来要列出 𝑚 个关系。

接下来 𝑚m 行,每行一个字符 𝑜𝑝𝑡 和两个整数 𝑝,𝑞,分别代表关系(朋友或敌人),有关系的两个人之中的第一个人和第二个人。其中 𝑜𝑝𝑡 有两种可能:

  • 如果 𝑜𝑝𝑡 为 F,则表明 𝑝 和 𝑞 是朋友。
  • 如果 𝑜𝑝𝑡 为 E,则表明 𝑝 和 𝑞 是敌人。

输出格式

一行一个整数代表最多的团体数。

输入输出样例

输入 #1

6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出 #1

3

        从题目中我们不难得知要维护的东西比较多,如果是朋友,就直接合并,如果是敌人的话,我们需要注意题意:一个人的朋友的朋友是朋友,一个人的敌人的敌人是朋友。也就是说,假如a和b互相对立,那么a和b的敌人就是朋友,我们需要将a和b的敌人合并,同理,也要将b与a的敌人合并,那怎么办呢?

        扩展域并查集就是通过将fa数组二开甚至多开通过元素在不同的域进行判断两两之间的关系的算法,这一题我们只需要维护两种关系,双开就好了,那什么是多开呢?

        假如我们有10个人的关系需要判断,我们就将fa数组多开一倍,初始化20个位置,将同一类放在1~10,11~20,这样就形成了两个区域,这就是拓展域的由来。在维护时,我们需要将朋友和天敌分开在不同的域中,也就是说,我们要将a和b的敌人合并,就要合并a和b+n,因为敌人之间是相差了一个域的。因此main函数需要这么改:

while(m --)
{
	char cmd;
	int x, y;
		
	cin >> cmd >> x >> y;
			
	if(cmd == 'F')
		merge(x, y);
	else
	{
		merge(x, y + n);
		merge(y, x + n);
	}
}	

        相比较于带权并查集,扩展域并查集相对比较好理解一些。

附上完整代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, ans = 0;
int fa[N];

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

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

int main()
{
	cin >> n >> m;
	
	for(int i = 1; i <= 2 * n; i ++)
		fa[i] = i;
		
	while(m --)
	{
		char cmd;
		int x, y;
		
		cin >> cmd >> x >> y;
			
		if(cmd == 'F')
			merge(x, y);
		else
		{
			merge(x, y + n);
			merge(y, x + n);
		}
	}	
	
	for(int i = 1; i <= n; i ++)
		if(fa[i] == i)
			ans ++;
			
	cout << ans << endl;
}

        其实昨天的食物链那题也可以用拓展域并查集做,只需要维护三种关系,同类,猎物,天敌就可以了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/665080.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

VBA语言専攻每周通知20240531

通知20240531 各位学员∶本周MF系列VBA技术资料增加616-620讲&#xff0c;T3学员看到通知后请免费领取,领取时间5月31日晚上19:00-6月1日晚上20:00。本次增加内容&#xff1a; MF616:创建具有间隔的计时器循环 MF617:计时器的计时与重置 MF618:列出单字符所有可能的排列组合…

怎么把图片大小调小?在线改图片大小的方法

怎么把比较大的图片压缩变小呢&#xff1f;在使用图片的时候&#xff0c;比较常见的一个问题就是图片太大导致无法正常上传&#xff0c;需要将图片处理到合适的大小之后&#xff0c;才可以正常在网上上传。现在一般调整图片大小多会通过使用在线改图片大小的在线工具来处理&…

动态路由协议实验——RIP

动态路由协议实验——RIP 什么是RIP ​ RIP(Routing Information Protocol,路由信息协议&#xff09;是一种内部网关协议&#xff08;IGP&#xff09;&#xff0c;是一种动态路由选择协议&#xff0c;用于自治系统&#xff08;AS&#xff09;内的路由信息的传递。RIP协议基于…

Codigger编码场景介绍(三):调试场景(Debug Scenery)

Codigger&#xff0c;一个专为开发人员设计的工具&#xff0c;致力于为不同的开发场景提供最佳的切换体验。Codigger囊括了多种场景&#xff0c;如传统场景、调试场景、设计器场景、驾驶舱场景以及纯净场景等。在上一篇文章中&#xff0c;我们介绍了驾驶舱场景&#xff0c;今天…

SpringBoot集成JOOQ加Mybatis-plus使用@Slf4j日志

遇到个问题记录下&#xff0c;就是SpringBoot使用Mybatis和Mybatis-plus时可以正常打印日志&#xff0c;但是JOOQ的操作日志确打印不出来&#xff1f; 下面的解决方法就是将JOOQ的日志单独配置出来&#xff0c;直接给你们配置吧&#xff01; 在项目的resources目录下创建日志…

windows11下将Labelme标注数据转为YOLOV5训练数据集

完整代码&#xff1a; import shutil import os import numpy as np import json from glob import glob import cv2 from sklearn.model_selection import train_test_split from utils.data_dir import root_dirdef convert(size, box):dw 1. / (size[0])dh 1. / (size[1]…

mysql大表的深度分页慢sql案例(跳页分页)-2

1 背景 有一张大表&#xff0c;内容是费用明细表&#xff0c;数据量约700万级&#xff0c; 普通B树索引KEY idx_fk_fymx_qybh_xfsj (qybh,xfsj)。 1.1 原始深度分页sql select t.* from fk_fymx t where t.qybh XXXXXXX limit 100000,100; 深度分页会导致加载数据行过多1000001…

详细解析Barlow Twins:自监督学习中的创新方法

首先先简单了解一下机器学习中&#xff0c;主要有三种学习范式&#xff1a;监督学习、无监督学习和自监督学习&#xff1a; 监督学习&#xff1a;依赖带标签的数据&#xff0c;通过输入输出映射关系进行训练。无监督学习&#xff1a;不依赖标签&#xff0c;关注数据的内在结构…

整合Spring Boot 框架集成Knife4j

本次示例使用Spring Boot作为脚手架来快速集成Knife4j,Spring Boot版本2.3.5.RELEASE ,Knife4j版本2.0.7 POM.XML完整文件代码如下&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0…

美创CTO周杰受邀参加2024省级现代服务业高研班,分享“人工智能数据安全与防护技术”

近日&#xff0c;为期三天的省级现代服务业“模型生态应用与安全治理”高级研修班在杭州成功举办。 本次高研班由浙江省人社厅、浙江省委网信办指导&#xff0c;浙江省网络空间安全协会主办&#xff0c;旨在抢抓新一轮人工智能带来的科技革命与产业变革新机遇&#xff0c;助推浙…

C++入门——类和对象【3】(6)

前言 本节是C类和对象中的最后一节&#xff0c;学完本节内容并且能够掌握之前所学的所有内容的话&#xff0c;C就可以说是入门了&#xff0c;那我们废话不多说&#xff0c;正式进入今天的学习 1. 再谈构造函数 1.1 引入 我们在栈的背景下来看 栈的代码&#xff1a; ​type…

Docker Hub 国内镜像源配置

Docker Hub 国内镜像源配置 Docker Hub 国内镜像源是指在国内境内提供 Docker 镜像服务的镜像源。由于国际网络带宽等问题&#xff0c;国内用户下载 Docker 镜像通常速度较慢。因此&#xff0c;为了解决这个问题&#xff0c;一些国内的公司和组织提供了 Docker 镜像的国内镜像…

什么是机器人离线编程? 衡祖仿真

一、什么是机器人离线编程&#xff1f; 机器人离线编程是自动化生产的重要一环。离线编程指&#xff0c;在建立了机器人的三维模拟场景后&#xff0c;经由软件仿真计算&#xff0c;生成控制机器人运动轨迹&#xff0c;进而生成机器人的控制指令。工程师可以由此来控制物理环境…

基于SSM框架的手机商城项目

后端: 订单管理 客户管理&#xff1a; 商品管理 类目管理 前端&#xff1a; 首页&#xff1a;

算法(十一)贪婪算法

文章目录 算法简介算法概念算法举例 经典问题 -背包问题 算法简介 算法概念 贪婪算法&#xff08;Greedy&#xff09;是一种在每一步都采取当前状态下最好的或者最优的选择&#xff0c;从而希望导致结果也是全局最好或者最优的算法。贪婪算法是当下局部的最优判断&#xff0c…

java向上转型

介绍 代码 父类 package b;public class father_ {//father classString name"动物";int age10;public void sleep() {System.out.println("睡");}public void run() {System.out.println("跑");}public void eat() {System.out.println("…

案例|开发一个美业小程序,都有什么功能

随着移动互联网的迅猛发展&#xff0c;美业连锁机构纷纷寻求数字化转型&#xff0c;以小程序为载体&#xff0c;提升服务效率&#xff0c;增强客户体验。 线下店现在面临的困境&#xff1a; 客户到店排队时间过长&#xff0c;体验感受差 新客引流难&#xff0c;老用户回头客…

实验---DC-AC逆变器(1)---EG8010+NSI6602驱动IGBT实验

一、设计电路 1.LCC 主回路模块原理图 1.1 电源部分 这个电源部分电路图是一个简单而有效的DC-DC转换器设计&#xff0c;包含输入保护和滤波、电源模块、以及输出滤波和稳定。 a. 输入电源部分 输入电源 (E12V): 电路从E12V端子接收12V的直流电源。这是整个电路的输入电源。…

【知识拓展】机器学习基础(二):什么是模型、自定义模型、模型训练、模型调优

前言 接上文&#xff0c;前文对模型没有过多介绍&#xff0c;随着看的资料增多&#xff0c;对模型有了更多的自我认识&#xff0c;记录一下。要了解模型&#xff0c;我们先从零开始创建一个模型开始&#xff1a; 最简单的方法是使用Python和scikit-learn库。关于scikit-learn库…

Maven 中的 classifier 属性用过没?

最近训练营有小伙伴问到松哥一个关于 Maven 依赖的问题&#xff0c;涉及到 classifier 属性&#xff0c;随机问了几个小伙伴&#xff0c;都说工作中没用到过&#xff0c;因此简单整篇文章和小伙伴们分享下。 Maven 大家日常开发应该都有使用&#xff0c;Maven 中有一个比较好玩…