当前位置: 首页 > 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…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

Appium下载安装配置保姆教程(图文详解)

目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...