当前位置: 首页 > 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;帮助你在实际开发中做出更合理…...

CentOS 7下PHP7.4编译安装全攻略:从依赖解决到常见报错处理

CentOS 7下PHP7.4编译安装全攻略&#xff1a;从依赖解决到常见报错处理 在Linux服务器环境中&#xff0c;PHP作为最流行的服务器端脚本语言之一&#xff0c;其安装方式通常有yum安装和编译安装两种选择。对于追求性能优化和功能定制的开发者来说&#xff0c;编译安装PHP7.4无疑…...

利用VMware虚拟机在本地模拟星图GPU平台环境测试MogFace-large

利用VMware虚拟机在本地模拟星图GPU平台环境测试MogFace-large 想试试最新的MogFace-large人脸检测模型&#xff0c;但手头没有现成的云GPU服务器&#xff1f;或者想先在本地环境里跑通流程&#xff0c;验证一下效果再上云&#xff1f;今天就来分享一个非常实用的方法&#xf…...

3步搞定Windows 11优化:用Win11Debloat让你的电脑更快更干净

3步搞定Windows 11优化&#xff1a;用Win11Debloat让你的电脑更快更干净 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本&#xff0c;用于从Windows中移除预装的无用软件&#xff0c;禁用遥测&#xff0c;从Windows搜索中移除Bing&#xff0c;以及执行各种其他更改以简…...

告别内存焦虑:用DiskANN在单机上搞定十亿向量检索的完整配置与调优指南

告别内存焦虑&#xff1a;用DiskANN在单机上搞定十亿向量检索的完整配置与调优指南 当你的推荐系统需要处理超过1亿条商品特征向量&#xff0c;或是生物医药团队要匹配数十亿分子结构时&#xff0c;传统内存索引方案会让服务器内存条价格直接突破年度预算。这时DiskANN就像一位…...

Hypervisor环境下高效进程间通信技术解析

1. Hypervisor环境下的进程通信挑战 在虚拟化技术大行其道的今天&#xff0c;Hypervisor环境下的进程间通信&#xff08;IPC&#xff09;已经成为系统性能的关键瓶颈。想象一下&#xff0c;你住在小区同一栋楼的两个单元里&#xff0c;明明直线距离只有10米&#xff0c;却要绕到…...

FLUX.1-dev开源镜像部署教程:像素幻梦免配置环境3步快速上手

FLUX.1-dev开源镜像部署教程&#xff1a;像素幻梦免配置环境3步快速上手 1. 像素幻梦简介 像素幻梦(Pixel Dream Workshop)是一款基于FLUX.1-dev扩散模型构建的像素艺术生成工具。它采用独特的16-bit像素风格界面设计&#xff0c;为创作者提供沉浸式的AI绘图体验。 与传统AI…...

深度学习赋能国税局发票查验:中英文混合验证码的高效识别方案

1. 验证码识别的税务场景痛点 每次打开国税局网站查验发票时&#xff0c;那个扭曲变形的中英文混合验证码是不是让你特别头疼&#xff1f;作为财务人员&#xff0c;我每天要处理上百张发票&#xff0c;手动输入这些验证码不仅效率低下&#xff0c;还容易出错。传统OCR技术在这里…...

AvrLib-fork:面向AVR的C++14零开销硬件抽象库

1. 项目概述AvrLib-fork 是一个面向 AVR 微控制器平台的高度类型安全、现代 C&#xff08;C14 兼容&#xff09;嵌入式库&#xff0c;专为 PlatformIO 生态系统深度优化设计。它并非 Arduino Core 的简单封装&#xff0c;而是一套从底层硬件抽象出发、以零开销抽象&#xff08;…...

小米Pad 5变身Windows生产力工具:完整驱动配置实战指南

小米Pad 5变身Windows生产力工具&#xff1a;完整驱动配置实战指南 【免费下载链接】MiPad5-Drivers Based on Surface Duo Drivers. 项目地址: https://gitcode.com/gh_mirrors/mi/MiPad5-Drivers 你是否想过将手中的小米Pad 5从娱乐平板转变为真正的生产力工具&#x…...

Terraria 源代码架构解析:从核心功能到启动配置的全方位指南

Terraria 源代码架构解析&#xff1a;从核心功能到启动配置的全方位指南 【免费下载链接】Terraria-Source-Code 项目地址: https://gitcode.com/gh_mirrors/te/Terraria-Source-Code Terraria 源代码项目是一款经典沙盒游戏的开源实现&#xff0c;包含了世界生成、实体…...