tarjan计算割点

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N=10005;
const int M=30005;

int n, m;
int head[N], E=0; // graph
int dfn[N], low[N], ts=0; // tarjan
int root, ans=0;

struct Edge{
    int v, ne;
}e[M];

inline void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
} 

void tarjan(int u){
    dfn[u]=low[u]=++ts;
    int cnt=0; // 统计u节点的子树数量
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u], low[v]);
            if(low[v]>=dfn[u]) ++cnt; // v是u的子树节点
        }
        else low[u]=min(low[u], dfn[v]); // v不是u的子树节点, 更新low[u]
    }
    if(u!=root) ++cnt; // u不是根节点, 去掉u后形成的子树计算父节点所在的子树
    ans=max(ans, cnt);
}

int main(){
    while(scanf("%d%d", &n, &m), n||m){
        memset(dfn, 0x00, sizeof dfn);
        memset(low, 0x00, sizeof low);
        memset(head, -1, sizeof head);
        E=ts=0;
        while(m--){
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        ans=0; // 删除点后连通块最多可以分成几部分
        int cnt=0; // 统计连通块的个数
        // 枚举图中的根节点
        for(root=0; root<n; ++root){
            if(!dfn[root]){
                ++cnt;
                tarjan(root);
            }
        }
        printf("%d\n", ans+cnt-1);
    }

    return 0;
}