poj 2117 Electricity【点双连通求删除点后最多的bcc数】

#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
#define MAX 21000
#define MAXM 2001000
#define INF 0x7fffff
using namespace std;
int dfn[MAX],low[MAX];
int dfsclock,ebccnt;
int addbcc[MAX];//记录去掉割点后bcc个数
int head[MAX],ans,num;
int iscut[MAX];//记录是否是割点
struct node
{
    int beg,end,next;
}edge[MAXM];
void init()
{
    ans=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
    edge[ans].beg=u;
    edge[ans].end=v;
    edge[ans].next=head[u];
    head[u]=ans++;
}
void tarjan(int u,int fa)
{
    int i,v;
    dfn[u]=low[u]=++dfsclock;
    int son=0;//记录子节点数目
    for(i=head[u];i!=-1;i=edge[i].next)
    {      
        v=edge[i].end;
        if(!dfn[v])
        {
            son++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v])//是割点，先不考虑是不是根节点
            {
                addbcc[u]++;//这是割点的一个子节点，bcc数目加1
                iscut[u]=1;
            }
        }
        else 
            low[u]=min(dfn[v],low[u]);
    }
    if(fa<0&&son<2)//不是根节点
    {
        iscut[u]=0;
        addbcc[u]=0;
    }
    if(fa<0&&son>1)//是根节点
    {
        iscut[u]=1;
        addbcc[u]=son-1;//这里当是根节点时去掉割点bcc数目为子节点数目son
                 //但是因为上边我们for循环中求bcc时全部当做非根节点求这样
                 //其非根节点割点去掉之后bcc个数 为son+1，为了最后输出时统一加1
                 //这里我们让 addbcc[u]=son-1;
    } 
}
void find(int l,int r)
{
    dfsclock=0;
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(addbcc,0,sizeof(addbcc));
    memset(iscut,0,sizeof(iscut));
    num=0;
    for(int i=l;i<=r;i++)
    {
        if(!dfn[i])
        {
        	tarjan(i,-1);
        	num++;//计算原始的图被分为几部分 
        }    
    }
}
int main()
{
    int n,m,j,i,a,b;
    while(scanf("%d%d",&n,&m),n|m)
    {
    	if(m==0)
    	{
    		printf("%d\n",n-1);
    		continue;
    	}
        init();
        while(m--)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        find(0,n-1);
        int sum=-1;
        for(i=0;i<n;i++) 
            sum=max(sum,addbcc[i]+num);
        printf("%d\n",sum);
    }
    return 0;
}