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

CF862B Mahmoud and Ehab and the bipartiteness(二分图的性质)

思路:一个二分图是由两个集合组成的,同一个集合中的节点间不能连边,所以一个二分图最多有cnt[1]*cnt[2]条边,题目给出一个树的n-1条边,要我们添加最多的边数使他成为二分图,添加的边数就是cnt[1]*cnt[2]-n+1条,所以我们先用dfs对每个节点进行染色,计算出两个个集合的节点数

Code:

constexpr int N=2e5+5,mod=1e9+7;int n;
int h[N],e[N],ne[N],idx;
int color[N],cnt[4];void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u,int c)
{color[u]=c;cnt[c]++;for(int i=h[u];~i;i=ne[i]){if(!color[e[i]]) dfs(e[i],3-c);}}void solve()
{ cin>>n;memset(h,-1,sizeof h);for(int i=1;i<=n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}  dfs(1,1);int sum=cnt[1]*cnt[2];cout<<sum-n+1;
}

相关文章:

CF862B Mahmoud and Ehab and the bipartiteness(二分图的性质)

思路&#xff1a;一个二分图是由两个集合组成的&#xff0c;同一个集合中的节点间不能连边&#xff0c;所以一个二分图最多有cnt[1]*cnt[2]条边&#xff0c;题目给出一个树的n-1条边&#xff0c;要我们添加最多的边数使他成为二分图&#xff0c;添加的边数就是cnt[1]*cnt[2]-n1…...

React Native 全栈开发实战班 :数据管理与状态之React Hooks 基础

在 React Native 应用中&#xff0c;数据管理与状态管理是构建复杂用户界面的关键。React 提供了多种工具和模式来处理数据流和状态管理&#xff0c;包括 React Hooks、Context API 以及第三方状态管理库&#xff08;如 Redux&#xff09;。本章节将详细介绍 React Hooks 的基础…...

传奇996_22——自动挂机

登录钩子函数中执行 callscript(actor, "../QuestDiary/主界面基础按钮/主界面基础按钮QM", "基础按钮QM")基础按钮QM执行了已下代码 #IF Equal <$CLIENTFLAG> 1 #ACT goto PC端面板加载#IF Equal <$CLIENTFLAG> 2 #ACT goto 移动端面板加载…...

faiss 提供了多种索引类型

faiss 多种索引类型 在 faiss 中&#xff0c;IndexFlatL2 是一个简单的基于 L2 距离&#xff08;欧几里得距离&#xff09;进行索引的索引类型&#xff0c;但实际上&#xff0c;faiss 提供了多种索引类型&#xff0c;支持不同的度量方式和性能优化&#xff0c;您可以根据需求选…...

比rsync更强大的文件同步工具rclone

背景 多个复制&#xff0c;拷贝&#xff0c;同步文件场景&#xff0c;最大规模的是每次几千万规模的小文件需要从云上对象存储中拉取到本地。其他的诸如定期数据备份&#xff0c;单次性数据备份。 rsync是单线程的&#xff0c;开源的mrsync是多线程的&#xff0c;但适用范围没…...

《业务流程--穿越从概念到实践的丛林》读后感一:什么是业务流程

1.1 流程和业务流程概念辨析 业务流程建模标准(BPMN)对于业务流程的定义:一个业务流程由为了配合一个组织性或技术环境而一系列活动组成。这些活动共同实现一个业务目标。 业务流程再造最有名的倡导者托马斯.H.达文波特对于流程和业务流程的定义:流程是一组结构化且可度量的…...

解决docker mysql命令行无法输入中文

docker启动时&#xff0c;设置支持中文 docker run --name mysql-container -e MYSQL_ROOT_PASSWORDroot -d mysql:5.7 --character-set-serverutf8mb4 --collation-serverutf8mb4_unicode_ci --default-time-zone8:00 进入docker时&#xff0c;指定LANG即可 docker exec -it …...

基于Java Springboot城市公交运营管理系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…...

Lc70--319.两个数组的交集(二分查找)---Java版

1.题目描述 2.思路 用集合求交集&#xff0c;因为集合里面的元素要满足不重复、无序、唯一。使得集合在去重、查找和集合操作&#xff08;如交集、并集、差集等&#xff09;中非常高效和方便。 3.代码实现 class Solution {public int[] intersection(int[] nums1, int[] nu…...

亿咖通科技应邀出席微软汽车行业智享会,分享ECARX AutoGPT全新实践

11月14日&#xff0c;全球出行科技企业亿咖通科技&#xff08;纳斯达克股票代码&#xff1a;ECX&#xff09;应邀于广州参加由微软举行的汽车行业智享会&#xff0c;揭晓了亿咖通科技对“AI定义汽车”时代的洞察与技术布局&#xff0c;分享了亿咖通科技汽车垂直领域大模型ECARX…...

Python教程:运算符重载

在Python中&#xff0c;运算符重载是通过定义特殊方法&#xff08;也称为魔术方法&#xff09;来实现的&#xff0c;这些特殊方法允许类的实例像内置类型那样使用运算符。 Python提供了一系列这样的特殊方法&#xff0c;用于重载各种运算符。 以下是一些常见的运算符重载特殊…...

AWTK VSCode 实时预览插件端口冲突的解决办法

AWTK XML UI 预览插件&#xff1a;在 vscode 中实时预览 AWTK XML UI 文件&#xff0c;在 Copilot 的帮助下&#xff0c;可以大幅提高界面的开发效率。 主要特色&#xff1a; 真实的 UI 效果。可以设置主题&#xff0c;方便查看在不同主题下界面的效果。可以设置语言&#xf…...

【MySQL系列】深入理解MySQL中的存储、排序字符集

前言 在创建数据库时&#xff0c;我们经常会需要填写数据库的所用字符集、排序规则&#xff0c;字符集和排序规则是两个非常重要的概念&#xff0c;它们决定了数据库如何存储和比较字符串数据。在 MySQL 中&#xff0c;常用的存储字符集有 utf8、utf8mb4&#xff0c;而排序字符…...

RPC-健康检测机制

什么是健康检测&#xff1f; 在真实环境中服务提供方是以一个集群的方式提供服务&#xff0c;这对于服务调用方来说&#xff0c;就是一个接口会有多个服务提供方同时提供服务&#xff0c;调用方在每次发起请求的时候都可以拿到一个可用的连接。 健康检测&#xff0c;能帮助从连…...

关于Java处理Excel常规列表记录,并入库的操作

1.描述 对于常规的Excel列表&#xff08;二维表格&#xff09;的入库处理&#xff0c;一般的mysql连接工具&#xff0c;例如Navicat就支持。但是&#xff0c;因为业务需要&#xff0c;不想每次都去手动导入&#xff0c;所以这里采用编码且定时任务的形式来实现。 2.Excel常规列…...

深入理解 JavaScript 中的 Array.find() 方法:原理、性能优势与实用案例详解

目录 深入理解 JavaScript 中的 Array.find() 方法&#xff1a;原理、性能优势与实用案例详解 一、引言&#xff1a;为什么要使用Array.find() 二、Array.find()的使用与技巧 1、基础语法 2、返回值 3、使用技巧 三、Array.find()的优势与实际应用案例 1、利用返回引用…...

计算机网络安全 —— 对称加密算法 DES (一)

一、对称加密算法概念# ​ 我们通过计算机网络传输数据时&#xff0c;如果无法防止他人窃听&#xff0c; 可以利用密码学技术将发送的数据变换成对任何不知道如何做逆变换的人都不可理解的形式&#xff0c; 从而保证了数据的机密性。这种变换被称为加密&#xff08; encryptio…...

5. ARM_指令集

概述 分类 汇编中的符号&#xff1a; 指令&#xff1a;能够编译生成一条32位机器码&#xff0c;并且能被处理器识别和执行伪指令&#xff1a;本身不是指令&#xff0c;编译器可以将其替换成若干条指令伪操作&#xff1a;不会生成指令&#xff0c;只是在编译阶段告诉编译器怎…...

Jenkins的pipeline Script的 每个组件的详细讲解

在Jenkins的Pipeline脚本中&#xff0c;各个组件的配置和Groovy的一些常用函数起到了决定性的作用&#xff0c;帮助开发人员控制自动化流程的执行。以下是对Jenkins Pipeline的主要组件和Groovy常用函数的详细讲解&#xff1a; 1. Jenkins Pipeline主要组件 1.1 agent 功能&…...

Tomcat 和 Netty 的区别及应用场景分析

在 Java Web 开发中&#xff0c;Tomcat 和 Netty 都是常见的网络框架&#xff0c;它们各自有着不同的设计理念和适用场景。本文将通过详细的对比和实际场景示例&#xff0c;帮助你理解 Tomcat 和 Netty 在功能、性能、架构等方面的差异&#xff0c;帮助你在实际开发中做出更合理…...

像素幻梦快速上手指南:3步完成16-bit风格图像生成与内存流导出

像素幻梦快速上手指南&#xff1a;3步完成16-bit风格图像生成与内存流导出 1. 认识像素幻梦创意工坊 像素幻梦创意工坊&#xff08;Pixel Dream Workshop&#xff09;是一款基于FLUX.1-dev扩散模型构建的像素艺术生成工具。它采用明亮的16-bit像素风格界面设计&#xff0c;为…...

像素幻梦·创意工坊部署教程:Mac M1/M2芯片原生运行FLUX.1-dev像素生成

像素幻梦创意工坊部署教程&#xff1a;Mac M1/M2芯片原生运行FLUX.1-dev像素生成 1. 前言&#xff1a;认识像素幻梦创意工坊 像素幻梦创意工坊(Pixel Dream Workshop)是一款专为像素艺术创作设计的AI工具&#xff0c;基于最新的FLUX.1-dev扩散模型构建。与传统的AI绘图工具不…...

LM386集成功放电路实战:从零搭建到波形调试全记录(附实测数据)

LM386集成功放电路实战&#xff1a;从零搭建到波形调试全记录&#xff08;附实测数据&#xff09; 在电子设计领域&#xff0c;音频功率放大器一直是基础却充满挑战的课题。LM386作为经典的集成功放芯片&#xff0c;以其低功耗、高增益和易用性著称&#xff0c;成为入门者和资深…...

【英一】考研英语一历年真题及答案解析PDF电子版(1980-2025年)

【英一】考研英语一历年真题及答案解析PDF电子版&#xff08;1980-2025年&#xff09;考试时间 2026年全国硕士研究生招生考试定于12月20日-21日进行。小编整理了提供1980-2025年考研英语一完整真题集&#xff0c;含权威答案解析。PDF高清版本支持直接打印&#xff0c;便于考生…...

想为小说配图?试试圣女司幼幽-造相Z-Turbo,我的真实使用体验

想为小说配图&#xff1f;试试圣女司幼幽-造相Z-Turbo&#xff0c;我的真实使用体验 1. 为什么我需要这个AI绘画工具 作为一名网络小说作者&#xff0c;我经常遇到一个难题&#xff1a;如何在社交媒体上为我的小说章节配上吸引人的插图。找画师定制价格昂贵&#xff0c;自己学…...

如何免费获取Microsoft Word APA第7版参考文献格式:完整安装指南

如何免费获取Microsoft Word APA第7版参考文献格式&#xff1a;完整安装指南 【免费下载链接】APA-7th-Edition Microsoft Word XSD for generating APA 7th edition references 项目地址: https://gitcode.com/gh_mirrors/ap/APA-7th-Edition 还在为学术论文的参考文献…...

企业内网安全集成:通义千问1.5-1.8B-Chat-GPTQ-Int4私有化部署与内网穿透方案

企业内网安全集成&#xff1a;通义千问1.5-1.8B-Chat-GPTQ-Int4私有化部署与内网穿透方案 最近和几个在企业做研发的朋友聊天&#xff0c;他们都在头疼同一个问题&#xff1a;公司内部有不少业务系统想用上大模型的能力&#xff0c;比如自动生成报告、智能客服、代码辅助这些&…...

告别虚拟机!在Windows 11上零配置搭建Masm汇编实验环境(保姆级图文教程)

在Windows 11上零配置搭建Masm汇编实验环境&#xff1a;从入门到实战 对于计算机专业的学生和开发者来说&#xff0c;汇编语言是理解计算机底层工作原理的重要工具。然而&#xff0c;传统的汇编环境搭建往往需要复杂的配置步骤或依赖虚拟机&#xff0c;这给初学者带来了不小的门…...

实战案例:用Fish Speech 1.5为视频添加多语言配音

实战案例&#xff1a;用Fish Speech 1.5为视频添加多语言配音 1. 引言&#xff1a;视频配音的新选择 在视频制作过程中&#xff0c;配音往往是耗时耗力的环节。传统配音需要专业录音棚、配音演员和后期处理&#xff0c;成本高且周期长。Fish Speech 1.5的出现为视频创作者提供…...

如何在普通PC上低成本部署Qwen3?VLLM轻量化配置指南

如何在普通PC上低成本部署Qwen3&#xff1f;VLLM轻量化配置指南 对于大多数个人开发者和小型团队来说&#xff0c;高性能服务器和顶级显卡往往是可望而不可及的奢侈品。但别担心&#xff0c;即使你只有一台普通PC&#xff0c;也能通过合理的配置和优化手段成功部署Qwen3这样的大…...