CodeForces - 1000E We Need More Bosses
2024-09-04 10:50:05
依然一眼题,求出割边之后把图缩成一棵树,然后直接求最长链就行了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;
}
最新文章
- 在uwp仿制WPF的Window
- 【Ubuntu日常技巧】VirtualBox多网卡路由配置,保障虚拟机连接上外网
- 软件测试 -- alpha测试和beta测试的区别
- 《Linux命令行大全》系列(三、Linux 系统)
- Create a custom configSection in web.config or app.config file
- RatingBar
- PAT (Advanced Level) 1051. Pop Sequence (25)
- Html5与CSS3权威指南 百度云下载
- OpenCV 读取视频 多种方式
- 微信app支付(android端+java后台)
- Java之split()方法
- python对Excel表格操作
- HDU - 6203:ping ping ping (DFS序 贪心)
- java代码示例(2)
- 强大的Android基地 论坛
- python获取指定目录下特定格式的文件名
- React + Ant Design网页,配置
- (三)Lua脚本语言入门(数组)
- 组织安全性SQL
- Oracle 12C -- 清空audit记录