[BZOJ1023]cactus仙人掌图——仙人掌直径

[BZOJ1023][SHOI2008]cactus仙人掌图

        仙人掌的直径。不在环上的边按照树处理，在环上的边先留下来，把从环上分岔处理完，再用单调队列环形DP处理。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int M=1e6+10;
int head[N],ver[2*M],nex[2*M],tot=1;
inline void add(int x,int y) {
    ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}
int dfn[N],low[N],num,stk[N],top,d[N],ans;
int c[2*N],v[2*N],cnt,q[2*N];
void solve_circle(){//单调队列处理环形DP
    int len=cnt;
    cnt=2*cnt;
    for(int i=len;i<cnt;++i)c[i]=c[i-len];
    int st=0,ed=-1;
    q[++ed]=0;v[0]=d[c[0]];
    for(int j=1;j<cnt;++j){
        v[j]=d[c[j]]-j;
        if(q[ed]-q[st]+1>(len>>1))++st;//len>>1因为要走环上短的一侧
        ans=max(ans,j+d[c[j]]+v[q[st]]);
        while(st<=ed&&v[q[ed]]<=v[j])--ed;
        q[++ed]=j;
    }
    int Max=0;
    for(int i=0;i<len-1;++i)
        Max=max(Max,min(len-1-i,i+1)+d[c[i]]);
    d[c[len-1]]=max(d[c[len-1]],Max);
}
void tarjan(int x,int fa) {
    dfn[x]=low[x]=++num;
    stk[++top]=x;
    for(int i=head[x]; i; i=nex[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) {
                --top;
                ans=max(ans,d[x]+d[y]+1);
                d[x]=max(d[x],d[y]+1);
            }else if(low[y]==dfn[x]){
                cnt=0;
                do{
                    c[cnt++]=stk[top];//保存环
                } while (stk[top--]!=y);
                c[cnt++]=x;
                solve_circle();
            }
        } else if(y!=fa)
            low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    int n,m,k,x,y;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i){
        scanf("%d%d",&k,&x);
        while(--k){
            scanf("%d",&y);
            add(x,y);add(y,x);
            x=y;
        }
    }
    tarjan(1,0);
    printf("%d",ans);
    return 0;
}