hdu 4612 双联通缩点+树形dp

#pragma comment(linker,"/STACK:102400000,102400000")//总是爆栈加上这个就么么哒了
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
#define N 210000
#define inf 99999999
struct node {
  int u,v,w,next;
}bian[N*20],biantwo[N*20];
int head[N],yong,dfn[N],low[N],yongtwo,index,top,cnt,stac[N],visit[N];
int suo[N];
void init(){
memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(visit,0,sizeof(visit));
index=0;top=0;cnt=0;yong=0;
yongtwo=0;
}
void addedge(int u,int v) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
void addedgetwo(int u,int v,int w) {
    biantwo[yongtwo].u=u;
    biantwo[yongtwo].v=v;
    biantwo[yongtwo].w=w;
    biantwo[yongtwo].next=head[u];
    head[u]=yongtwo++;
}
int Min(int a,int b) {
return a>b?b:a;
}
void tarjan(int u,int pre) {//双联通缩点
int i;
dfn[u]=low[u]=++index;
stac[++top]=u;
visit[u]=1;
for(i=head[u];i!=-1;i=bian[i].next) {
    int v=bian[i].v;
    if(i==(pre^1))continue;
     if(!dfn[v]) {
        tarjan(v,i);
        low[u]=Min(low[u],low[v]);
     }
     else
        if(visit[v])
        low[u]=Min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
    ++cnt;
    int t;
    do{
        t=stac[top--];
        suo[t]=cnt;
        visit[t]=0;
    }while(t!=u);
}
}
int dis[N],n;
int bfs(int u) {//求树的直径
int i,vis[N],j;
  queue<int>q;
  memset(vis,0,sizeof(vis));
  for(i=1;i<=cnt;i++)
    dis[i]=inf;
  q.push(u);
  vis[u]=1;
  dis[u]=0;
  while(!q.empty()) {
    int d=q.front();
    q.pop();
    for(i=head[d];i!=-1;i=biantwo[i].next) {
        int v=biantwo[i].v;
        if(vis[v]==0&&dis[v]>dis[d]+biantwo[i].w){
            dis[v]=dis[d]+biantwo[i].w;
            vis[v]=1;
            q.push(v);
        }
    }
  }
  int mi=inf,temp;
  //printf("%d %d
",dis[1],dis[2]);
  for(i=1;i<=cnt;i++)
  if(mi>dis[i]) {
    mi=dis[i];
    temp=i;
  }
 // printf("%d
",mi);
  return temp;
}
int main() {
     int  m,i,j;
     while(scanf("%d%d",&n,&m),n||m) {
        init();
        while(m--){
            scanf("%d%d",&i,&j);
            addedge(i,j);
            addedge(j,i);
        }
        tarjan(1,-1);
        memset(head,-1,sizeof(head));
        for(i=0;i<yong;i++) {
            int u=bian[i].u,v=bian[i].v;
            if(suo[u]!=suo[v]) {
                addedgetwo(suo[u],suo[v],-1);
                addedgetwo(suo[v],suo[u],-1);
            }
        }
        printf("%d
",cnt+dis[bfs(bfs(1))]-1);
     }
return 0;
}