题意

最少添加多少条边,使无向图有欧拉回路。

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 ;
}

最新文章

  1. 敏捷转型历程 - Sprint3 Grooming
  2. 利用Python进行数据分析(14) pandas基础: 数据转换
  3. selenium 测试框架中使用grid
  4. R12供应商地点层付款方法SQL
  5. Jquery简单瀑布流代码示例
  6. TestNg依赖详解(三)------灵活的文件配置依赖
  7. redis 库相关命令
  8. 【C语言】编写一个函数实现n^k,使用递归实现
  9. BAT-使用BAT方法判断网络启动EXE(快捷方式)
  10. 【转】Java中 List的遍历
  11. mfc EDIT字体颜色
  12. 让Linux开机运行命令
  13. RAC下一个Fatal NI connect error 12170.错误处理
  14. NancyFx 2.0的开源框架的使用-Basic
  15. 项目管理之 Objective-C 编码规范
  16. Activity中finish()和onDestroy()的区别
  17. Ext.grid.EditorGridPanel分页和查看全部
  18. [Java第一课]环境变量的配置以及eclipse一些常用快捷键
  19. 织梦去除tag标签url中的问号
  20. Springboot+Mybatis整合PageHelper

热门文章

  1. 3.多线程传参,以及tuple数组
  2. mysql裸文件备份XtraBackup (innobackupex)
  3. Aspose WorkbookDesigner打开文件异常"Error xml namespace"
  4. PostGIS解析Geometry几何对象
  5. Linux 文件系统的层次化结构
  6. mysql给某字段随机赋特定范围的整数值
  7. hadoop-11-ambari-server安装
  8. [Webpack + React] Import CSS Modules with TypeScript and webpack
  9. Ordered Broadcast有序广播
  10. java线程共享受限资源 解决资源竞争 thinking in java4 21.3