给定一个由 n 个点 m 条边构成的无向图,请你求出该图删除一个点之后,连通块最多有多少
#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=30005;
int n,m;
int h[N],e[M],ne[M],idx;
int low[N],dfn[N],tim;
int root,ans;
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
int cnt=0;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tarjan(j);
low[u]=min(low[u],low[j]);
if(low[j]>=dfn[u])
cnt++;
}
else
low[u]=min(low[u],dfn[j]);
}
if(u!=root&&cnt)
cnt++;
ans=max(ans,cnt);
}
int main(){
while(cin>>n>>m,n||m){
memset(h,-1,sizeof(h));
memset(dfn,0,sizeof(dfn));
idx=tim=ans=0;
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
int cnt=0;
for(root=0;root<n;root++)
if(!dfn[root]){
cnt++;
tarjan(root);
}
cout<<ans+cnt-1<<endl;
}
return 0;
}