We Need More Bosses CodeForces - 1000E (无向图缩点)
2024-09-01 14:39:31
大意: 给定无向连通图, 定义两个点$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);
}
最新文章
- java集合你了解多少?
- asp.net MVC中获取当前URL/Controller/Action
- UNIX环境高级编程笔记之标准I/O库
- Topic Model
- 在SQL Server中 获取日期、日期格式转换
- C#_观察者模式
- 搭建SSH框架所需Jar包及其解释
- XianBicycle
- 1.Repeater控件
- 安卓手机用-----Exchange Activesync---同步Gmail日历联系人
- OpenWrt compiles
- How to set custom JsonSerializerSettings for Json.NET in MVC 4 Web API?
- javascript中的几种遍历方法浅析
- mongo分布式集群搭建手记
- numpy库补充 mean函数应用
- [Hadoop]Hadoop章2 HDFS原理及读写过程
- 【worker】js中的多线程
- STL之set和map
- 微信小程序入门教程(一)API接口数据记录
- java实现文件监控