CF209C Trails and Glades(欧拉路)
2024-08-29 04:07:50
题意
最少添加多少条边,使无向图有欧拉回路。
n,m≤106
题解
求出每个点的度数
奇度数点需要连一条新边
仅有偶度数点的连通块需要连两条新边
答案为上面统计的新边数 / 2
注意:此题默认以1为起点,有重边自环。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
const int N=;
int n,m,fa[N],vis[N],deg[N],flag[N],num,anss,ans;
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void merge(int x,int y){
int a=find(x);
int b=find(y);
if(a==b)return;
fa[a]=b;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)fa[i]=i;
vis[]=;
for(int i=,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
if(a!=b){
deg[a]++;deg[b]++;
vis[a]=vis[b]=;
merge(a,b);
}
else vis[a]=;
}
for(int i=;i<=n;i++){
if(deg[i]&){
flag[find(i)]++;
}
}
for(int i=;i<=n;i++)
if(vis[i]&&i==find(i)){
if(flag[i])ans+=flag[i];
else anss++;
num++;
}
ans/=;
if(num==)printf("%d",ans);
else printf("%d",ans+anss);
return ;
}
最新文章
- 敏捷转型历程 - Sprint3 Grooming
- 利用Python进行数据分析(14) pandas基础: 数据转换
- selenium 测试框架中使用grid
- R12供应商地点层付款方法SQL
- Jquery简单瀑布流代码示例
- TestNg依赖详解(三)------灵活的文件配置依赖
- redis 库相关命令
- 【C语言】编写一个函数实现n^k,使用递归实现
- BAT-使用BAT方法判断网络启动EXE(快捷方式)
- 【转】Java中 List的遍历
- mfc EDIT字体颜色
- 让Linux开机运行命令
- RAC下一个Fatal NI connect error 12170.错误处理
- NancyFx 2.0的开源框架的使用-Basic
- 项目管理之 Objective-C 编码规范
- Activity中finish()和onDestroy()的区别
- Ext.grid.EditorGridPanel分页和查看全部
- [Java第一课]环境变量的配置以及eclipse一些常用快捷键
- 织梦去除tag标签url中的问号
- Springboot+Mybatis整合PageHelper
热门文章
- 3.多线程传参,以及tuple数组
- mysql裸文件备份XtraBackup (innobackupex)
- Aspose WorkbookDesigner打开文件异常"Error xml namespace"
- PostGIS解析Geometry几何对象
- Linux 文件系统的层次化结构
- mysql给某字段随机赋特定范围的整数值
- hadoop-11-ambari-server安装
- [Webpack + React] Import CSS Modules with TypeScript and webpack
- Ordered Broadcast有序广播
- java线程共享受限资源 解决资源竞争 thinking in java4 21.3