[그림 의 연관 성] poj 2117 Electricity

http://poj.org/problem?id=2117
제목 설명: 무 방향 그림 에 n (n < = 10000) 개의 점 m 변 (연결 되 지 않 음) 이 있 으 며, 임의의 점 을 삭제 할 수 있 습 니 다.최대 연결 블록 수량 을 구하 세 요.
이 문 제 는 매우 길지 만, 유용 한 것 은 단지 몇 마디 뿐이다.징 그 럽 지?
이 문 제 는 tarjon 알고리즘 으로 절단 점 을 구 하 는 것 으로 절단 점 에 주의 하 는 것 은 상대 성 이 있다.한 마디 로 물 문제 다.
특 판 m = 0 의 경우 에 주의 하 세 요.

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 10011
#define MAXM 200000050
using namespace std;

struct node
{
    int v ;
    node *next ;
}edge[MAXM] ,*num[MAXN] ,*code=edge ;

void add(int a,int b)
{
    node *p=++code ;
    p->v=b ,p->next=num[a] ;
    num[a]=p ;
}

int n ,m ,rtson ,ans ,out ,a ,b ,cnt ,pos ;
int low[MAXN] ,dfn[MAXN] ;

void dfs(int u,int fa)
{
    dfn[u]=low[u]=++cnt;
    int v ,temp=0 ;
    for(node *p=num[u];p!=NULL;p=p->next)
        if((v=p->v)!=fa)
        {
            if(!dfn[v])
            {
                dfs(v,u);
                low[u]=min(low[u],low[v]);
                if(low[v]>=dfn[u])
                {
                    if(fa==-1)
                        ++rtson;
                    else ++temp;
                }
            }
            else low[u]=min(low[u],dfn[v]);
        }
    ans=max(ans,temp+1);
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&n+m)
    {
        if(m==0)
        {
            printf("%d
",n-1);
            continue;
        }
        memset(num,0,sizeof(num));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        code=edge ,cnt=pos=ans=out=0 ;

        for(int i=0;i<m;++i)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        for(int i=0;i<n;++i)
            if(!dfn[i])
            {
                ++pos;
                rtson=0;
                dfs(i,-1);
                if(rtson>1)
                    ans=max(ans,rtson);
                out=max(out,ans);
            }
        printf("%d
",pos+out-1);
    }
    return 0;
}