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

【P2860】[USACO06JAN] Redundant Paths G - Harvey

题意

给定一个连通图,求最少要加多少条边使得图无割边。

思路

首先,我们可以先缩点再进行考虑。
缩点后整个连通图变成一棵树,为了使连边后不出现割边,可以将所有度为 \(1\) 的点两两连边,如果度为 \(1\) 的点的个数为奇数,则可以往任意一个点连边,连完之后所有点的度都大于等于 \(2\),此时可以证明连通图是一个边双连通分量,所以得出结论:连边数等于度为 \(1\) 的节点个数除以 \(2\) 向上取整

code

#include<bits/stdc++.h>
#define ll long longusing namespace std;const ll N = 5e5+5,M = 2e6+5;
ll n,m;
ll x,y;
ll son,cnt,tot,idx;struct edge{ll to;ll next;
}e[M<<1];ll head[N],dfn[N],low[N],vis[N],dcc[N],edcc[N],sum;
void add(ll u,ll v){++tot;e[tot]=(edge){v,head[u]};head[u]=tot;
}
stack<ll> s;
void tarjan(ll u,ll fa){dfn[u]=low[u]=++cnt;s.push(u);for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;if(!dfn[v]){tarjan(v,u);low[u]=min(low[u],low[v]);if(low[v]>low[u]){dcc[v]++,dcc[u]++;}}else {low[u]=min(low[u],low[v]);}}if(low[u]==dfn[u]){sum++;ll tt;do{tt=s.top();s.pop();edcc[tt]=sum;}while(tt!=u);}
}int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;add(x,y),add(y,x);}tarjan(1,-1); for(int i=1;i<=n;i++){if(dcc[i]){vis[edcc[i]]+=dcc[i];}}ll ans=0;for(int i=1;i<=sum;i++){if(vis[i]==1)ans++;}cout<<(ans+1>>1);return 0;
}
http://www.hskmm.com/?act=detail&tid=15888

相关文章:

  • GUI软件构造
  • 企业微信客服API模式接入第三方客服系统,对接大模型AI智能体
  • react使用ctx和reducer代替redux
  • KM 乱记
  • 深入解析:B树与B+树的原理区别应用
  • linux中的服务监控,停用自动重启
  • RHEL7/CentOS7 install NVIDIA drivers and CUDA
  • 浅谈 Burnside 和 Polya 的证明
  • 算法学习笔记:支配对
  • 西电PCB设计指南第5章学习笔记
  • ImageMagick - 关于图片压缩,通过dk整理的一些可用指令 - window64
  • 【杂记】原 hack
  • 全新升级!EasyDSS会议管理3大核心功能,让远程协作更高效
  • 黄金、原油期货数据API对接文档
  • 我的笔记方案
  • 聊聊前序、中序、后序表达式
  • flink书籍 - --
  • 详述大模型备案
  • Asp.Net Core 鉴权授权
  • 124
  • 我的笔记记录方案
  • AT_arc156_d [ARC156D] Xor Sum 5
  • iOS Provisioning Profile 证书 描述文件
  • 计算快速付氏变换FFT前需要加窗函数
  • 直播预告| PostgreSQL 与 IvorySQL 在云原生时代的演进与实践
  • KGDB(Kernel GNU Debugger)工具使用方法详解 - 详解
  • Wallpaper Engine v2.7.3 动态壁纸软件-内含数百款动态皮肤 - 实践
  • 力扣155题 最小栈
  • Markdown语法
  • 压垮项目经理的“三座大山”:时间、成本、质量的生存法则与破局工具