hdu 4612 Warm up双連通+樹形dp思想

Warm up
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 3160    Accepted Submission(s): 718
Problem Description
　　N planets are connected by M bidirectional channels that allow instant transportation. It's always possible to travel between any two planets through these channels.
　　If we can isolate some planets from others by breaking only one channel , the channel is called a bridge of the transportation system.
People don't like to be isolated. So they ask what's the minimal number of bridges they can have if they decide to build a new channel.
　　Note that there could be more than one channel between two planets.
 
Input
　　The input contains multiple cases.
　　Each case starts with two positive integers N and M , indicating the number of planets and the number of channels.
　　(2<=N<=200000, 1<=M<=1000000)
　　Next M lines each contains two positive integers A and B, indicating a channel between planet A and B in the system. Planets are numbered by 1..N.
　　A line with two integers '0' terminates the input.
 
Output
　　For each case, output the minimal number of bridges after building a new channel in a line.
 
Sample Input

  
    

     
   4 4
1 2
1 3
1 4
2 3
0 0 
  
    

 
Sample Output

  
    

     
   0
  
    
  
    


  
    

         題意:所与の図の中のすべての橋の数量を求めて、縮み点の後の最も長い鎖を減らして、つまり題の中で求めた答え(実際に縮み点を使わなくても求めることができる)
        考え方の参考:http://blog.csdn.net/qq172108805/article/details/9564705

#include "stdio.h"   //          dp   
#include "string.h"
#pragma comment(linker,"/STACK:102400000,102400000")   //      （        ）

#define N 201000
#define M 1001000

struct node
{
    int x,y;
    bool visit;  //        
    int next;
}edge[4*M];
int idx,head[N];

inline int MIN(int a,int b){ return a<b?a:b; }

void Init()
{
    idx=0;
    memset(head,-1,sizeof(head));
}
void Add(int x,int y)
{
    edge[idx].x = x;
    edge[idx].y = y;
    edge[idx].visit = false; //          
    edge[idx].next = head[x];
    head[x] = idx++;
}

int n,m;
int sum,temp;
int low[N],dfn[N],time;
int dp1[N],dp2[N];

void DFS(int x)
{
    int i,y;
    dp1[x] = dp2[x] = 0;
    low[x] = dfn[x] = ++time;
    for(i=head[x]; i!=-1; i=edge[i].next)
    {
        if(edge[i].visit) continue;
        y = edge[i].y;
        edge[i].visit = edge[i^1].visit = true;
        if(!dfn[y]) // y     
        {
            DFS(y);
            low[x] = MIN(low[x],low[y]);
            if(low[y] > dfn[x])
                sum++;  //     ，sum++
            temp = dp1[y];
            if(low[y] > dfn[x])
                temp++;
            if(temp > dp1[x])
            {
                dp2[x] = dp1[x];
                dp1[x] = temp;
            }
            else if(temp > dp2[x])
                dp2[x] = temp;
        }
        else
            low[x] = MIN(low[x],dfn[y]);
    }
}

int main()
{
    int i;
    int x,y;
    while(scanf("%d %d",&n,&m),n||m)
    {
        Init();
        for(i=0; i<m; ++i)
        {
            scanf("%d %d",&x,&y);
            Add(x,y);
            Add(y,x);
        }
        sum = 0;  //        
        time = 1;
        memset(dfn,0,sizeof(dfn));
        DFS(1);
        int dist=0;   //                 （       ）(        )
        for(i=1; i<=n; ++i) 
        {
            if(dist<dp1[i]+dp2[i])  //dp1[i]+dp2[i]    i        
                dist = dp1[i]+dp2[i];
        }
        printf("%d
",sum - dist);//              ，    
    }
    return 0;
}