大意: 给定无向连通图, 定义两个点$s,t$个价值为切断一条边可以使$s,t$不连通的边数. 求最大价值.

显然只有桥会产生贡献. 先对边双连通分量缩点建树, 然后求直径即为答案.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std; const int N = 3e5+10;
int n,m,clk,ans,cnt;
int dfn[N],low[N],dep[N],q[N],bcc[N];
vector<int> g[N],gg[N]; void dfs(int x, int fa) {
dfn[x]=low[x]=++clk;
q[++*q] = x;
for (int y:g[x]) if (y!=fa) {
if (dfn[y]) low[x]=min(low[x],dfn[y]);
else {
dfs(y,x);
low[x] = min(low[x],low[y]);
}
}
if (low[x]==dfn[x]) {
++cnt;
do bcc[q[*q]] = cnt; while (q[(*q)--]!=x);
}
}
void dfs2(int x, int fa) {
for (int y:gg[x]) if (y!=fa) {
dfs2(y,x);
ans = max(ans, dep[x]+dep[y]+1);
dep[x] = max(dep[x],dep[y]+1);
}
}
int main() {
scanf("%d%d", &n, &m);
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
g[u].pb(v),g[v].pb(u);
}
dfs(1,0);
REP(i,1,n) for (int j:g[i]) {
if (bcc[i]!=bcc[j]) {
gg[bcc[i]].pb(bcc[j]);
}
}
dfs2(1,0);
printf("%d\n", ans);
}

最新文章

  1. java集合你了解多少?
  2. asp.net MVC中获取当前URL/Controller/Action
  3. UNIX环境高级编程笔记之标准I/O库
  4. Topic Model
  5. 在SQL Server中 获取日期、日期格式转换
  6. C#_观察者模式
  7. 搭建SSH框架所需Jar包及其解释
  8. XianBicycle
  9. 1.Repeater控件
  10. 安卓手机用-----Exchange Activesync---同步Gmail日历联系人
  11. OpenWrt compiles
  12. How to set custom JsonSerializerSettings for Json.NET in MVC 4 Web API?
  13. javascript中的几种遍历方法浅析
  14. mongo分布式集群搭建手记
  15. numpy库补充 mean函数应用
  16. [Hadoop]Hadoop章2 HDFS原理及读写过程
  17. 【worker】js中的多线程
  18. STL之set和map
  19. 微信小程序入门教程(一)API接口数据记录
  20. java实现文件监控

热门文章

  1. 【零基础】神经网络优化之dropout和梯度校验
  2. 微信小程序侧边栏滑动特效(左右滑动)
  3. JAVA RDD 介绍
  4. p2p通信原理及实现
  5. C# 使用Task执行异步操作
  6. Oracle数据库的坑
  7. Visual studio 正在从以下位置加载符号:Microsoft符号服务器 尝试取消禁用后续符号加载
  8. node.js写巨大的xlsx
  9. .NET C#获取当前网页地址信息
  10. Flutter 弹出键盘屏幕溢出问题