题目大意
给定一张图，找到两个点，使得这两个点之间的所有路径必须经过的边最多。
思路分析
我们先来思考一下如果已知两个点，怎么求两个点之间必须经过的边的数量。
在一般的无向连通图中，我们容易发现，其实答案就是两点所在的边双连通分量之间的割边数量。
- 显然这就是割边的定义之一。
而我们又知道另一个性质：如果把图缩点成一颗树，那么树上的边与原图中的割边一一对应。
- 还是很显然，想想我们缩点是怎么缩的。
因此，我们就可以轻松的得到做法：先把图缩点成一颗树，再求树的直径。
（这不就是板子套板子吗
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1200100;//300000*2*2（双向边，两张图
int n,m,idx=1,cnt,in1,in2,num,p,q;
int to[N],nxt[N],head[N],rhead[N];
int dfn[N],low[N],bridge[N],rid[N];
int dis[N];
void add(int h[],int u,int v){idx++;to[idx]=v;nxt[idx]=h[u];h[u]=idx;}
void tarjan(int s,int last){
dfn[s]=low[s]=++cnt;
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(i==(last^1)) continue;
if(!dfn[v]){
tarjan(v,i);
low[s]=min(low[s],low[v]);
if(dfn[s]<=low[v]){bridge[i]=bridge[i^1]=1;}//找桥
}
else low[s]=min(low[s],dfn[v]);
}
}
void dfs_0(int s){
rid[s]=num;//记录点所在的连通分量
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(bridge[i]||rid[v]) continue;
dfs_0(v);
}
}
void dfs_1(int s,int fa,int &u){
for(int i=rhead[s];i;i=nxt[i]){
int v=to[i];
if(v==fa) continue;
dis[v]=dis[s]+1;
if(dis[0]<dis[v]){dis[0]=dis[v];u=v;}//找树的直径
dfs_1(v,s,u);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&in1,&in2);
add(head,in1,in2);
add(head,in2,in1);
}
tarjan(1,-1);
for(int i=1;i<=n;i++)
if(!rid[i]){num++;dfs_0(i);}
for(int s=1;s<=n;s++)
for(int i=head[s];i;i=nxt[i])
if(rid[s]!=rid[to[i]]){
add(rhead,rid[s],rid[to[i]]);//只用加一次，因为另一个点也会加一次
}
dis[1]=0;dfs_1(1,0,p);
dis[0]=dis[p]=0;dfs_1(p,0,q);//两遍dfs求树的直径
cout<<dis[0]<<'\n';
return 0;
}