边双联通分量缩点+树的直径——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<<],e_c[maxn<<];

int head[maxn],tot,head_c[maxn],tot_c,n,m;

void init(){

    memset(head,-,sizeof head);

    memset(head_c,-,sizeof head_c);

    tot=tot_c=;

}

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!=-;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^].b=;

        }

        else if(i!=(in_edge^))

            low[x]=min(low[x],dfn[y]);

    }

}

int c[maxn],dcc;

void dfs1(int x){

    c[x]=dcc;

    for(int i=head[x];i!=-;i=e[i].nxt){

        int y=e[i].to;

        if(e[i].b || c[y]!=)continue;

        dfs1(y);

    }

}

int dp[maxn],ans;

void dfs2(int x,int pre){

    for(int i=head_c[x];i!=-;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]+);

        dp[x]=max(dp[x],dp[y]+);

    }

}

int main(){

    init();

    cin>>n>>m;int u,v;

    for(int i=;i<=m;i++){

        cin>>u>>v;

        add(u,v);add(v,u);

    }

    tarjan(,-);

    for(int i=;i<=n;i++)

        if(!c[i]){

            ++dcc;

            dfs1(i);

        }

    for(int i=;i<tot;i++){

        int x=e[i].to,y=e[i^].to;

        if(c[x]!=c[y])

            add_c(c[x],c[y]);

    }

    dfs2(,);

    cout<<ans<<'\n';

}