<题目链接>

题目大意:
给定一个$n$个节点$m$条边的无向图,问你对任意两点,最多有多少条特殊边,特殊边指删除这条边后,这两个点不能够到达。

解题分析:

特殊变其实就是指割边,题意就是问你任意两点的路径之间,割边的最大数量。比较裸的题目,由边双连通和树的直径拼凑而成。

用边双连通缩完点之后,树形DP算出最长链即可。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T&x){
x=;int f=;char ch=getchar();
while(ch<'' ||ch>''){ if(ch=='-')f=-; ch=getchar(); }
while(ch>='' && ch<=''){ x=x*+ch-''; ch=getchar(); }
x*=f;
}
#define pb push_back
#define REP(i,s,t) for(int i=s;i<=t;i++)
#define clr(a,b) memset(a,b,sizeof(a))
const int N = 3e5+;
int n,m,tot,top,bcc;
int head1[N],head2[N],dfn[N],bel[N],cnt1,cnt2;
int low[N],instk[N],stk[N];
vector<int>G[N];
struct Edge{ int from,to,nxt; }e1[N<<],e2[N<<];
int ans;
inline void init(){
REP(i,,n)G[i].clear();
cnt1=cnt2=tot=top=bcc=;
clr(dfn,);clr(bel,);
clr(head1,-);clr(head2,-);
}
inline void add1(int u,int v){
e1[cnt1]=(Edge){u,v,head1[u]};head1[u]=cnt1++;
}
inline void add2(int u,int v){
e2[cnt2]=(Edge){u,v,head2[u]};head2[u]=cnt2++;
}
void Tarjan(int u,int pre){
dfn[u]=low[u]=++tot;
instk[u]=;stk[++top]=u;
bool fp=false;
for(int i=head1[u];~i;i=e1[i].nxt){
int v=e1[i].to;
if(v==pre && !fp){ fp=true;continue; }
if(!dfn[v]){
Tarjan(v,u);
low[u]=min(low[u],low[v]);
}else if(instk[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++bcc;
while(true){
int v=stk[top--];
instk[v]=;
bel[v]=bcc;
G[bcc].pb(v);
if(u==v)break;
}
}
}
inline void getMap(){
for(int i=;i<cnt1;i++){ //缩点
int u=e1[i].from,v=e1[i].to;
if(bel[u]!=bel[v])add2(bel[u],bel[v]);
}
} int dp1[N],dp2[N];
//树形DP求树的直径
void dfs(int u,int pre){
for(int i=head2[u];~i;i=e2[i].nxt){
int v=e2[i].to;
if(v==pre)continue;
dfs(v,u);
if(dp1[v]+>dp1[u])dp2[u]=dp1[u],dp1[u]=dp1[v]+;
else if(dp1[v]+>dp2[u])dp2[u]=dp1[v]+;
}
ans=max(ans,dp1[u]+dp2[u]);
} int main(){
init();
read(n);read(m);
REP(i,,m){
int u,v;read(u);read(v);
add1(u,v);add1(v,u);
}
Tarjan(,-);
getMap();
dfs(,-); //进行树形DP求最长链
cout<<ans<<endl;
}

最新文章

  1. 在firefox浏览器下,scrollTop始终为0的问题
  2. BLE教程 - 官方tutorial翻译
  3. 分享一些Hadoop环境搭建所用到的软件
  4. ExtJS笔记 Form
  5. Win 8.1 下 安装 SQL2005
  6. SAP S4 Finance6个支持企业实时财务管理的主要创新领域
  7. hdoj 1237 简单计算器
  8. C#是怎么获取窗口标题的
  9. 转: 理解 JMeter 聚合报告(Aggregate Report)
  10. POJ 2154 Color [Polya 数论]
  11. org.springframework.beans.factory.CannotLoadBeanClassException-估计mapper出参 和 po字段不对应了
  12. Android设备管理器&mdash;&mdash;DevicePolicyManager
  13. 如何访问https的网站?-【httpclient】
  14. JMeter的__threadGroupName使用注意事项
  15. ros bashrc 无法source setup.sh
  16. 牛客网 牛客练习赛7 B.购物-STL(priority_queue)
  17. SQL Server 2008R2 代理服务-开启
  18. CODING 告诉你硅谷的研发项目管理之道系列(6)
  19. 「 Luogu P1850 」 换教室
  20. MySQL启动不了 错误3

热门文章

  1. openstack stein部署手册 4. glance
  2. Codeforces Round #426 (Div. 2) - A
  3. Python语言为什么被称为高级程序设计语言?
  4. springboot框架中的各种 注解
  5. c#代码规则,C#程序中元素的命名规范
  6. [CF846A]Curriculum Vitae题解
  7. C++ 运算符优先级顺序表 (最新/完整)
  8. [CSP-S模拟测试]:甜圈(线段树)
  9. cordova+vue做的app解决引入cordova-plugin-splashscreen后启动先显示黑屏在显示启动页
  10. UVA 11752 The Super Powers(暴力)