二染色,CF 1594D - The Number of Imposters
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
1594D - The Number of Imposters |
二、解题报告
1、思路分析
并查集,扩展域并查集,带边权并查集详解,OJ练习,详细代码_拓展域并查集-CSDN博客
一眼类似于扩展域并查集可解决的问题
这个题就是在玩太空狼人杀
好人不说谎,坏人不吐真
A说B是坏人,那么A、B一定是不同阵营的
A说B是好人,那么A、B一定是同一阵营的
这是简单的数理逻辑
那么我们可以根据关系建图,从而二染色
我们并不关注哪个颜色是好人,我们对每个连通块选取颜色最多的那个作为坏人的数目即可
具体实现:
相同阵营,说明颜色相同,边权为0,传颜色传c ^ 0
不同阵营,说明颜色不同,边权为1,传颜色传c ^ 1
另:py递归爆内存,用栈来递归
2、复杂度
时间复杂度: O(N + M)空间复杂度:O(N + M)
3、代码详解
import sys
from math import infinput = lambda: sys.stdin.readline().strip()
MII = lambda: map(int, input().split())
LMI = lambda: list(map(int, input().split()))
LI = lambda: list(input())
II = lambda: int(input())
fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
P = 10**9 + 7def solve():n, m = MII()g = [[] for _ in range(n)]for _ in range(m):a, b, s = input().split()a, b = map(int, [a, b])a -= 1b -= 1w = 1 if s[0] == 'i' else 0g[a].append([b, w])g[b].append([a, w])color = [-1] * ncnt = [0, 0]def dfs(x: int, y: int) -> bool:stk = [x]color[x] = ycnt[y] += 1while stk:u = stk[-1]stk.pop()c = color[u]for v, w in g[u]:if ~color[v] and color[v] != c ^ w:return Falseelif color[v] == -1:stk.append(v)color[v] = c ^ wcnt[c ^ w] += 1return Trueres = 0for i in range(n):if ~color[i]:continuecnt = [0, 0]if not dfs(i, 0):print(-1)returnres += fmax(cnt[0], cnt[1])print(res)if __name__ == "__main__":T = 1T = II()for _ in range(T):solve()
相关文章:

二染色,CF 1594D - The Number of Imposters
目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 1594D - The Number of Imposters 二、解题报告 1、思路分析 并查集&…...

Go语言并发编程-Channel通信_2
Channel通信 Channel概述 不要通过共享内存的方式进行通信,而是应该通过通信的方式共享内存 这是Go语言最核心的设计模式之一。 在很多主流的编程语言中,多个线程传递数据的方式一般都是共享内存,而Go语言中多Goroutine通信的主要方案是Cha…...

Richteck立锜科技电源管理芯片简介及器件选择指南
一、电源管理简介 电源管理组件的选择和应用本身的电源输入和输出条件是高度关联的。 输入电源是交流或直流?需求的输出电压比输入电压高或是低?负载电流多大?系统是否对噪讯非常敏感?也许系统需要的是恒流而不是稳压 (例如 LED…...
Socket 简介与 Java Socket 编程示例
Socket(套接字)是网络通信中的一个关键概念,它是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象。 一、定义与概念 基本概念:Socket可以被视为网络环境中进程间通信的API(应用程序编程接口)&…...

跟着操作,解决iPhone怎么清理内存难题
在如今智能手机功能日益强大的时代,我们使用手机拍照、录制视频、下载应用、存储文件等操作都会占用手机内存。当内存空间不足时,手机运行会变得缓慢,甚至出现卡顿、闪退等现象。因此,定期清理iPhone内存是非常必要的。那么&#…...

React、Vue的password输入框组件,如何关闭自动填充?
有时候我们的表单使用了一个password组件,这时候每次打开新建,都会自动获取浏览器缓存的密码,但是它的上一个input输入框并不是用户名,这时候我们希望我们的表单,每次点开的时候密码是空的,让用户自动输入&…...

HTML+JS+CSS计算练习
可填 题目数量 数字范围 计算符号 题目做完后会弹窗提示正确率、用时 效果图 源代码在图片后面 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevic…...
设计模式使用场景实现示例及优缺点(行为型模式——责任链模式)
在一个遥远的森林深处,有一个和谐的动物王国。这个王国里的动物们都有各自的职责,大家相互合作,共同维护着森林的和平与繁荣。 一天,森林里来了一只迷路的小兔子,她焦急地四处张望,不知道该怎么办。于是&am…...

CSS-1_0 CSS和文档流
文章目录 CSS和文档流如何证明这个流的存在呢?流和display番外:inline-block 碎碎念 CSS和文档流 首先什么叫流呢? 通常来说,我们最终看到的网页是HTML文档中定义的各个元素挨个输出的结果,这种一个接一个输出的方式…...

小程序图片下载保存方法,图片源文件保存!
引言 现在很多时候我们在观看到小程序中的图片的时候,想保存图片的原文件格式的话,很多小程序是禁止保存的,即使是让保存的话,很多小程序也会限制不让保存原文件,只让保存一些分辨率很低的,非常模糊的图片…...

新书速览|深入理解Hive:从基础到高阶:视频教学版
《深入理解Hive:从基础到高阶:视频教学版》 本书内容 《深入理解Hive:从基础到高阶:视频教学版》采用“理论实战”的形式编写,通过大量的实例,结合作者多年一线开发实战经验,全面地介绍Hive的使用方法。《深入理解Hiv…...

钡铼Profinet、EtherCAT、Modbus、MQTT、Ethernet/IP、OPC UA分布式IO系统BL20X系列耦合器
BL20X系列耦合器是钡铼技术开发的一款用于分布式I/O系统的设备,专为工业环境下的高速数据传输和远程设备控制而设计,支持多种工业以太网协议,包括Profinet、EtherCAT、Modbus、MQTT、Ethernet/IP和OPC UA等。如果您正在考虑部署BL20X系列耦合…...

Git分支合并以及分支部分合并 提交记录合并
Git分支合并,以及分支部分合并,提交记录合并 最近工作中用到git分支合并的场景,记录一下. 分支整体合并,合并所有记录 仅合并分支部分代码...

IDEA关联数据库
《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试(Debug) 第七章 …...
【Leetcode】14. 最长公共前缀
leetcode原地址:https://leetcode.cn/problems/longest-common-prefix 描述 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入:strs [“flower”,“flow”,“flight”…...

【BUG】已解决:zipfile.BadZipFile: File is not a zip file
已解决:zipfile.BadZipFile: File is not a zip file 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页,我是博主英杰,211科班出身,就职于医疗科技公司,热衷分享知识,武汉城市开发…...

小白新手搭建个人网盘
小白新手搭建个人网盘 序云服务器ECS重置密码远程连接ECS实例 安装OwnCloud安装Apache服务PHP运行环境NAS挂载挂载验证操作体验 序 阿里云文件存储NAS(Apsara File Storage NAS)是一个可大规模共享访问,弹性扩展的分布式文件系统。本文主要是…...

NineData全面支持PostgreSQL可视化表结构设计
“PostgreSQL 是最像 Oracle 的开源关系型数据库“,也正因为如此,很多企业都青睐 PostgreSQL,拿它当成 Oracle 的替代品。所以毫无疑问,目前 PostgreSQL 在企业中非常常见。 对于直接接触 PostgreSQL 的开发人员而言,…...

从系统层面认识Linux及mysql中的多表查询
为什么计算机起始时间是1970年1月1日 为什么计算机起始时间是1970年1月1日-CSDN博客https://blog.csdn.net/csdn_kou/article/details/81535452 date "%Y-%m-%d %H:%M:%S" 查看日期 sudo ln -s /usr/share/zoneinfo/Asia/Shanghai /etc/localtime 在数据层面 CPU不…...

PCB(印制电路板)制造涉及的常规设备
印制电路板(PCB)的制造涉及多种设备和工艺。从设计、制作原型到批量生产,每个阶段都需要不同的专业设备。以下是一些在PCB制造过程中常见的设备: 1. 计算机辅助设计(CAD)软件: - 用于设计PC…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...

10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...