题意:给一个无向图,问最少加几条边变成边-双联通

题解:求一次双联通,缩点,这样就变成了一棵树,结果就是(树上的叶子节点+1)/2,叶子节点可以通过入度判断

#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std;
using namespace __gnu_cxx; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; vector<int>v[N];
int dfn[N],low[N];
int index,num;
map<int,int>ma[N];
void tarjan(int u,int f)
{
low[u]=dfn[u]=++index;
for(int i=;i<v[u].size();i++)
{
int x=v[u][i];
if(x==f)continue;
if(!dfn[x])
{
tarjan(x,u);
low[u]=min(low[u],low[x]);
if(low[x]>dfn[u])ma[x][u]=ma[u][x]=;
}
else low[u]=min(low[u],dfn[x]);
}
}
void dfs(int u,int f)
{
dfn[u]=num;
for(int i=;i<v[u].size();i++)
{
int x=v[u][i];
if(x!=u&&!dfn[x]&&!ma[x][u])dfs(x,u);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
v[a].pb(b);
v[b].pb(a);
}
index=num=;
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i,-);
memset(dfn,,sizeof dfn);
for(int i=;i<=n;i++)
if(!dfn[i])
{
++num;
dfs(i,-);
}
memset(low,,sizeof low);
for(int i=;i<=n;i++)
{
for(int j=;j<v[i].size();j++)
{
if(dfn[i]!=dfn[v[i][j]])
{
low[dfn[i]]++;
low[dfn[v[i][j]]]++;
}
}
}
int ans=;
for(int i=;i<=num;i++)
{
// cout<<low[i]<<endl;
if(low[i]==)
ans++;
}
printf("%d\n",(ans+)/);
return ;
}
/************ ************/

最新文章

  1. ListView+CheckBox实现全选 单击效果
  2. An unknown server-side error occurred while processing the command.处理
  3. 看项目得到info_freeCsdn-01闪屏页面
  4. 在JAVA中使用JSONObject生成json
  5. ActionResult 常见问题
  6. initEvent vs initMouseEvent
  7. php-mysql 问题笔记一——在命令行中可以执行的sql语句,无法从php页面页面执行!
  8. 华为CloudIDE免费公测,带你出坑带你飞
  9. 浅谈new/delete和malloc/free的用法与区别
  10. JS中$含义和用法
  11. 「JavaScript面向对象编程指南」原型
  12. 前端面试必备的css盒子模型
  13. js的点滴
  14. time 与 datetime 模块的常用方法
  15. QML 从入门到放弃
  16. 用于主题检测的临时日志(c5ac07a5-5dab-45d9-8dc2-a3b27be6e507 - 3bfe001a-32de-4114-a6b4-4005b770f6d7)
  17. python 4
  18. 搭建Modelsim SE仿真环境-使用do文件仿真
  19. 常用代码之二:使用BackgroundWorker或Task让代码异步执行。
  20. 使用jsonp进行跨站点数据访问

热门文章

  1. 给jquery easy-ui 添加右键菜单
  2. Eclipse中Copy Qualified Name复制类全名解决办法
  3. 【JMeter4.0学习(七)】之配置元素
  4. web应用的负载均衡、集群、高可用(HA)解决方案
  5. UVA 699 The Falling Leaves (二叉树水题)
  6. 从外置U盘中拷文件到Linux(挂载)
  7. 已备份数据库的磁盘结构版本号为611,server支持版本号为539,无法还原或升级数据库
  8. c# 当前不会命中断点 未载入该文档
  9. IOS发送带附件的邮件
  10. rm -rf 删除文件找回