二染色,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…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...