Tarjan

求最大的连通块的个数，在跑Tarjan时可以算出原本这个图中连通块的个数，在判断割点时记录一个数组代表删除这个点可以多加多少个连通块，如果不是根节点的话，回溯的还要加一个。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e8+5;
int n,m;
int group,ans;
int cnt,head[N];
struct edge {
    int to,nex;
} e[M] ;
inline void add(int u,int v) {
    e[++cnt].to=v,e[cnt].nex=head[u],head[u]=cnt;
    e[++cnt].to=u,e[cnt].nex=head[v],head[v]=cnt;
}
struct Tarjan {
    int dfn[N],low[N],tim;
    int cut[N],root,tp[N];
    void clr() {
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(cut,0,sizeof(cut));
        memset(tp,0,sizeof(tp));
        tim=0;
    }
    void tarjan(int u) {
        int flag=0;
        low[u]=dfn[u]=++tim;
        for(int i=head[u];i;i=e[i].nex) {
            int v=e[i].to;
            if(!dfn[v]) {
                flag++;
                tarjan(v);
                low[u]=min(low[u],low[v]);
                if((root==u&&flag>1)||(root!=u&&dfn[u]<=low[v])) cut[u]=true;
                if(dfn[u]<=low[v]) tp[u]++;
            } else {
                low[u]=min(low[u] ,dfn[v]);
            }
        }
        if(u!=root) tp[u]+=1;
    }
} T;
void Clear() {
    memset(head,0,sizeof(head));
    cnt=0,group=0,ans=0;
    T.clr();
}
int main() {
    while(1) {
        Clear();
        scanf("%d%d",&n,&m);
        if(!n) break;
        for(int i=1,a,b;i<=m;++i) {
            scanf("%d%d",&a,&b);
            add(a+1,b+1);
        }
        for(int i=1;i<=n;++i)
            if(!T.dfn[i]){
                ++group;
                T.root=i;
                T.tarjan(i);
            }
        for(int i=1;i<=n;++i)
            ans=max(ans,group+T.tp[i]-1) ;
        printf("%d\n",ans) ;
    }
}