Codeforces 1000E We Need More Bosses (边双连通+最长链)

<题目链接>

题目大意：
给定一个$n$个节点$m$条边的无向图，问你对任意两点，最多有多少条特殊边，特殊边指删除这条边后，这两个点不能够到达。

解题分析：

特殊变其实就是指割边，题意就是问你任意两点的路径之间，割边的最大数量。比较裸的题目，由边双连通和树的直径拼凑而成。

用边双连通缩完点之后，树形DP算出最长链即可。

#include <bits/stdc++.h>

using namespace std;

template<typename T>

inline void read(T&x){

    x=;int f=;char ch=getchar();

    while(ch<'' ||ch>''){ if(ch=='-')f=-; ch=getchar(); }

    while(ch>='' && ch<=''){ x=x*+ch-''; ch=getchar(); }

    x*=f;

}

#define pb push_back

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define clr(a,b) memset(a,b,sizeof(a))

const int N = 3e5+;

int n,m,tot,top,bcc;

int head1[N],head2[N],dfn[N],bel[N],cnt1,cnt2;

int low[N],instk[N],stk[N];

vector<int>G[N];

struct Edge{ int from,to,nxt; }e1[N<<],e2[N<<];

int ans;

inline void init(){

    REP(i,,n)G[i].clear();

    cnt1=cnt2=tot=top=bcc=;

    clr(dfn,);clr(bel,);

    clr(head1,-);clr(head2,-);

}

inline void add1(int u,int v){

    e1[cnt1]=(Edge){u,v,head1[u]};head1[u]=cnt1++;

}

inline void add2(int u,int v){

    e2[cnt2]=(Edge){u,v,head2[u]};head2[u]=cnt2++;

}

void Tarjan(int u,int pre){

    dfn[u]=low[u]=++tot;

    instk[u]=;stk[++top]=u;

    bool fp=false;

    for(int i=head1[u];~i;i=e1[i].nxt){

        int v=e1[i].to;

        if(v==pre && !fp){ fp=true;continue; }

        if(!dfn[v]){

            Tarjan(v,u);

            low[u]=min(low[u],low[v]);

        }else if(instk[v])low[u]=min(low[u],dfn[v]);

    }

    if(dfn[u]==low[u]){

        ++bcc;

        while(true){

            int v=stk[top--];

            instk[v]=;

            bel[v]=bcc;

            G[bcc].pb(v);

            if(u==v)break;

        }

    }

}

inline void getMap(){

    for(int i=;i<cnt1;i++){        //缩点

        int u=e1[i].from,v=e1[i].to;

        if(bel[u]!=bel[v])add2(bel[u],bel[v]);

    }

}

int dp1[N],dp2[N];

//树形DP求树的直径

void dfs(int u,int pre){

    for(int i=head2[u];~i;i=e2[i].nxt){

        int v=e2[i].to;

        if(v==pre)continue;

        dfs(v,u);

        if(dp1[v]+>dp1[u])dp2[u]=dp1[u],dp1[u]=dp1[v]+;

        else if(dp1[v]+>dp2[u])dp2[u]=dp1[v]+;

    }

    ans=max(ans,dp1[u]+dp2[u]);

}

int main(){

    init();

    read(n);read(m);

    REP(i,,m){

        int u,v;read(u);read(v);

        add1(u,v);add1(v,u);

    }

    Tarjan(,-);

    getMap();

    dfs(,-);        //进行树形DP求最长链

    cout<<ans<<endl;

}