题面在这里!

依然一眼题,求出割边之后把图缩成一棵树,然后直接求最长链就行了2333

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
const int N=300005; vector<int> g[N];
int dfn[N],low[N],num=1,hd[N],n,m,ans=0,v[N];
int to[N*2],ne[N*2],cnt,col[N],mx[N],dc;
bool ban[N*2]; inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;} void tarjan(int x,int fa){
dfn[x]=low[x]=++dc; for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa)
if(!dfn[to[i]]){
tarjan(to[i],x);
low[x]=min(low[x],low[to[i]]);
if(low[to[i]]>dfn[x]) ban[i]=ban[i^1]=1;
}
else low[x]=min(low[x],dfn[to[i]]);
} void B(int x){
col[x]=cnt; for(int i=hd[x];i;i=ne[i])
if(ban[i]){
if(col[to[i]]&&v[to[i]]!=cnt){
v[to[i]]=cnt;
g[cnt].pb(col[to[i]]);
g[col[to[i]]].pb(cnt);
}
}
else if(!col[to[i]]) B(to[i]);
} void dfs(int x,int fa){
for(int i:g[x]) if(i!=fa){
dfs(i,x),ans=max(ans,mx[i]+1+mx[x]);
mx[x]=max(mx[x],mx[i]+1);
}
} int main(){
scanf("%d%d",&n,&m);
int uu,vv;
for(int i=1;i<=m;i++){
scanf("%d%d",&uu,&vv);
add(uu,vv),add(vv,uu);
} tarjan(1,0); for(int i=1;i<=n;i++) if(!col[i]){
cnt++,B(i);
} dfs(1,0); printf("%d\n",ans);
return 0;
}

最新文章

  1. 在uwp仿制WPF的Window
  2. 【Ubuntu日常技巧】VirtualBox多网卡路由配置,保障虚拟机连接上外网
  3. 软件测试 -- alpha测试和beta测试的区别
  4. 《Linux命令行大全》系列(三、Linux 系统)
  5. Create a custom configSection in web.config or app.config file
  6. RatingBar
  7. PAT (Advanced Level) 1051. Pop Sequence (25)
  8. Html5与CSS3权威指南 百度云下载
  9. OpenCV 读取视频 多种方式
  10. 微信app支付(android端+java后台)
  11. Java之split()方法
  12. python对Excel表格操作
  13. HDU - 6203:ping ping ping (DFS序 贪心)
  14. java代码示例(2)
  15. 强大的Android基地 论坛
  16. python获取指定目录下特定格式的文件名
  17. React + Ant Design网页,配置
  18. (三)Lua脚本语言入门(数组)
  19. 组织安全性SQL
  20. Oracle 12C -- 清空audit记录

热门文章

  1. YII 框架查询
  2. Plant (矩阵快速幂)
  3. CCC2018游记
  4. bzoj 2809 左偏树\平衡树启发式合并
  5. bzoj 1034 贪心
  6. linux中使用mysql数据库
  7. Linux下用freetds执行SQL Server的sql语句和存储过程
  8. android 与JS之间的交互
  9. ajax之深入解析(2)
  10. django “如何”系列3:如何编写模型域(model filed)