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

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

MLP实战二:MLP 实现图像数字多分类

任务 实战&#xff08;二&#xff09;&#xff1a;MLP 实现图像多分类 基于 mnist 数据集&#xff0c;建立 mlp 模型&#xff0c;实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入&#xff0c;可视化图形数字&#xff1b; 2、完成数据预处理&#xff1a;图像数据维度转换与…...

Python异步编程:深入理解协程的原理与实践指南

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 持续学习&#xff0c;不断…...

Q1起重机指挥理论备考要点分析

Q1起重机指挥理论备考要点分析 一、考试重点内容概述 Q1起重机指挥理论考试主要包含三大核心模块&#xff1a;安全技术知识&#xff08;占40%&#xff09;、指挥信号规范&#xff08;占30%&#xff09;和法规标准&#xff08;占30%&#xff09;。考试采用百分制&#xff0c;8…...