当前位置: 首页 > news >正文

二染色,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概述 不要通过共享内存的方式进行通信&#xff0c;而是应该通过通信的方式共享内存 这是Go语言最核心的设计模式之一。 在很多主流的编程语言中&#xff0c;多个线程传递数据的方式一般都是共享内存&#xff0c;而Go语言中多Goroutine通信的主要方案是Cha…...

Richteck立锜科技电源管理芯片简介及器件选择指南

一、电源管理简介 电源管理组件的选择和应用本身的电源输入和输出条件是高度关联的。 输入电源是交流或直流&#xff1f;需求的输出电压比输入电压高或是低&#xff1f;负载电流多大&#xff1f;系统是否对噪讯非常敏感&#xff1f;也许系统需要的是恒流而不是稳压 (例如 LED…...

Socket 简介与 Java Socket 编程示例

Socket&#xff08;套接字&#xff09;是网络通信中的一个关键概念&#xff0c;它是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象。 一、定义与概念 基本概念&#xff1a;Socket可以被视为网络环境中进程间通信的API&#xff08;应用程序编程接口&#xff09;&…...

跟着操作,解决iPhone怎么清理内存难题

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

React、Vue的password输入框组件,如何关闭自动填充?

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

HTML+JS+CSS计算练习

可填 题目数量 数字范围 计算符号 题目做完后会弹窗提示正确率、用时 效果图 源代码在图片后面 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevic…...

设计模式使用场景实现示例及优缺点(行为型模式——责任链模式)

在一个遥远的森林深处&#xff0c;有一个和谐的动物王国。这个王国里的动物们都有各自的职责&#xff0c;大家相互合作&#xff0c;共同维护着森林的和平与繁荣。 一天&#xff0c;森林里来了一只迷路的小兔子&#xff0c;她焦急地四处张望&#xff0c;不知道该怎么办。于是&am…...

CSS-1_0 CSS和文档流

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

小程序图片下载保存方法,图片源文件保存!

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

新书速览|深入理解Hive:从基础到高阶:视频教学版

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

钡铼Profinet、EtherCAT、Modbus、MQTT、Ethernet/IP、OPC UA分布式IO系统BL20X系列耦合器

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

Git分支合并以及分支部分合并 提交记录合并

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

IDEA关联数据库

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …...

【Leetcode】14. 最长公共前缀

leetcode原地址&#xff1a;https://leetcode.cn/problems/longest-common-prefix 描述 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀&#xff0c;返回空字符串 “”。 示例 1&#xff1a; 输入&#xff1a;strs [“flower”,“flow”,“flight”…...

【BUG】已解决:zipfile.BadZipFile: File is not a zip file

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

小白新手搭建个人网盘

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

NineData全面支持PostgreSQL可视化表结构设计

“PostgreSQL 是最像 Oracle 的开源关系型数据库“&#xff0c;也正因为如此&#xff0c;很多企业都青睐 PostgreSQL&#xff0c;拿它当成 Oracle 的替代品。所以毫无疑问&#xff0c;目前 PostgreSQL 在企业中非常常见。 对于直接接触 PostgreSQL 的开发人员而言&#xff0c;…...

从系统层面认识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(印制电路板)制造涉及的常规设备

印制电路板&#xff08;PCB&#xff09;的制造涉及多种设备和工艺。从设计、制作原型到批量生产&#xff0c;每个阶段都需要不同的专业设备。以下是一些在PCB制造过程中常见的设备&#xff1a; 1. 计算机辅助设计&#xff08;CAD&#xff09;软件&#xff1a; - 用于设计PC…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...