http://acm.hdu.edu.cn/showproblem.php?pid=4587
给出一幅无向图，问除去两个点之后子图的最大联通分量个数。
考虑每次ban一个点然后跑一遍tarjin统计下数量即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #include<cstring> 5 using namespace std; 6 #define LL long long 7 #define pb push_back 8 const int maxn=5010; 9 vector<int>g[maxn]; 10 int dfn[maxn],low[maxn],sub[maxn],root,sum,ban; 11 bool vis[maxn]; 12 void dfs(int u){ 13 dfn[u]=low[u]=sum++; 14 vis[u]=1; 15 int son=0; 16 for(int i=0;i<g[u].size();++i){ 17 int v=g[u][i]; 18 if(v==ban)continue; 19 if(vis[v]){ 20 low[u]=min(low[u],dfn[v]); 21 } 22 else{ 23 dfs(v); 24 if(u==root)son++; 25 else{ 26 if(low[v]>=dfn[u])sub[u]++; 27 } 28 low[u]=min(low[u],low[v]); 29 } 30 } 31 if(u==root)sub[u]=son; 32 else sub[u]++; 33 } 34 int main(){ 35 int i,j,u,v,n,m; 36 while(scanf("%d%d",&n,&m)==2){ 37 for(i=0;i<n;++i){ 38 vis[i]=sub[i]=0; 39 g[i].clear(); 40 } 41 while(m--){ 42 scanf("%d%d",&u,&v); 43 g[u].pb(v); 44 g[v].pb(u); 45 } 46 int ans=0; 47 for(i=0;i<n;++i){ 48 ban=i; 49 int p=0; 50 sum=0; 51 memset(vis,0,sizeof(vis)); 52 memset(sub,0,sizeof(sub)); 53 for(j=0;j<n;++j){ 54 if(j==ban||vis[j])continue; 55 root=j; 56 dfs(j); 57 p++; 58 } 59 for(j=0;j<n;++j){ 60 if(j==ban)continue; 61 if(ans<sub[j]+p-1) ans=sub[j]+p-1; 62 } 63 } 64 printf("%d ",ans); 65 } 66 return 0; 67 }