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\n",dis[1],dis[2]);

  for(i=1;i<=cnt;i++)

  if(mi>dis[i]) {

    mi=dis[i];

    temp=i;

  }

 // printf("%d\n",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\n",cnt+dis[bfs(bfs(1))]-1);

     }

return 0;

}
巴特西

hdu 4612 双联通缩点+树形dp

最新文章

热门文章
