边双联通分量缩点+树的直径——cf1000E

题意理解了就很好做

题意：给一张无向图，任意取两个点s，t，s->t的路径上必经边数量为k

求这样的s,t,使得k最大

#include<bits/stdc++.h>
#define maxn 300005
using namespace std;
struct Edge{int to,nxt,b;}e[maxn<<1],e_c[maxn<<1];
int head[maxn],tot,head_c[maxn],tot_c,n,m;
void init(){
    memset(head,-1,sizeof head);
    memset(head_c,-1,sizeof head_c);
    tot=tot_c=0;
}
void add(int u,int v){
    e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++;
}
void add_c(int u,int v){
    e_c[tot_c].to=v;e_c[tot_c].nxt=head_c[u];head_c[u]=tot_c++;
}

int ind,low[maxn],dfn[maxn];
void tarjan(int x,int in_edge){
    low[x]=dfn[x]=++ind;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])
                e[i].b=e[i^1].b=1;
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],dfn[y]);
    }
}
int c[maxn],dcc;
void dfs1(int x){
    c[x]=dcc;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int y=e[i].to;
        if(e[i].b || c[y]!=0)continue;
        dfs1(y);
    }
}

int dp[maxn],ans;
void dfs2(int x,int pre){
    for(int i=head_c[x];i!=-1;i=e_c[i].nxt){
        int y=e_c[i].to;
        if(y==pre)continue;
        dfs2(y,x);
        ans=max(ans,dp[x]+dp[y]+1);
        dp[x]=max(dp[x],dp[y]+1);
    }
}

int main(){
    init();
    cin>>n>>m;int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    tarjan(1,-1);
    
    for(int i=1;i<=n;i++)
        if(!c[i]){
            ++dcc;
            dfs1(i); 
        }
    
    for(int i=0;i<tot;i++){
        int x=e[i].to,y=e[i^1].to;
        if(c[x]!=c[y])
            add_c(c[x],c[y]);
    }
    
    dfs2(1,1);
    
    cout<<ans<<'
';
}