题目描述
求一张图删除一个点后，最多被分为几个连通块。
思路
如果一个点被删除了，图会被分成两个及以上连通块，那么这个点一定是割点。也就是说，对于一张图，我们在判断割点时，当u为割点时，以u为根的搜索子树下一定会形成至少一个点双联通分量，所以我们只要每次判断u是割点时对cut[u]++，不过原图未保证是连通图，所以我们还需要把答案加上连通块的数量。因为我们算割点时删除至少形成两个点双联通分量，实质上将减1和加1抵消了。
#include <bits/stdc++.h> using namespace std; const int N=11000,M=2e6+10; int read() { int res=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();} return res*w; } int nxt[M],to[M],tot,head[N]; void add_edge(int x,int y) { nxt[tot]=head[x]; head[x]=tot; to[tot]=y; ++tot; } int dfn[N],low[N],idx,root,cut[N]; void tarjan(int u) { dfn[u]=low[u]=++idx; int cnt=0; for(int i=head[u];~i;i=nxt[i]) { int v=to[i]; if(!dfn[v]) { cnt++; tarjan(v); low[u]=min(low[u],low[v]); if((root==u&&cnt>1)||(dfn[u]<=low[v]&&root!=u)) cut[u]++; } else low[u]=min(low[u],dfn[v]); } } void clear() { memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(cut,0,sizeof(cut)); tot=0;idx=0; } int main() { int n,m; while(~scanf("%d%d",&n,&m)&&(m|n)) { clear(); if(m==0) { printf("%d ",n-1); continue ; } for(int i=1;i<=m;i++) { int x=read()+1,y=read()+1; add_edge(x,y);add_edge(y,x); } int cnt=0; for(int i=1;i<=n;i++) if(!dfn[i]) { root=i; cnt++; tarjan(i); } int ans=0; for(int i=1;i<=n;i++) if(cut[i])ans=max(ans,cut[i]); printf("%d ",ans+cnt); } }