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

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...