題面

1525
一句話題意：求一個圖刪除一個點之后，聯(lián)通塊最多有多少。（就是原題，沒啥好精簡的）

思路

刪去了一個點之后，多的連通塊個數(shù)相當于它的子樹個數(shù)（就是dfn沒更新過的那些點，不包括dfn更新過的點）。
注意：根節(jié)點增加的是子樹個數(shù)減一，不然你會WA。
因此在Tarjin的大框架下沒有什么要大改的地方。下面是代碼：

void tarjin(int k)
{
  dfn[k]=low[k]=++tot;
  int cntt=0;
  for(int i=head[k]; i; i=a[i].nxt)
    if(!dfn[a[i].to])
    {
      tarjin(a[i].to),cntt++,low[k]=min(low[k],low[a[i].to]);
      if(low[a[i].to]>=dfn[k]&&k!=rt) f[k]++;
    }
    else low[k]=min(low[k],dfn[a[i].to]);
  if(k==rt) f[k]=cntt-1;
}

最后的答案由兩部分組成：①原有的連通塊個數(shù) ②刪掉一個點，最多的增加量（最大的f）。
代碼長這樣（我把tarjin和輸入的一部分包含進去了）

 for(int i=1; i<=n; i++) if(!dfn[i]) rt=i,tarjin(i),ansn++;
    for(int i=1; i<=n; i++) ans=max(ans,f[i]);
    printf("%d\n",ans+ansn),scanf("%d%d",&n,&m);

代碼

直接上代碼，不多說。

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,f[10005],ansn,ans;
int head[10005],cnt,rt;
int dfn[10005],low[10005],tot;
struct node
{
  int nxt,to;
} a[1000005];
void add(int x,int y)
{
  a[++cnt].to=y,a[cnt].nxt=head[x],head[x]=cnt;
}
void tarjin(int k)
{
  dfn[k]=low[k]=++tot;
  int cntt=0;
  for(int i=head[k]; i; i=a[i].nxt)
    if(!dfn[a[i].to])
    {
      tarjin(a[i].to),cntt++,low[k]=min(low[k],low[a[i].to]);
      if(low[a[i].to]>=dfn[k]&&k!=rt) f[k]++;
    }
    else low[k]=min(low[k],dfn[a[i].to]);
  if(k==rt) f[k]=cntt-1;
}
int main()
{
  scanf("%d%d",&n,&m);
  while(n!=0)
  {
    memset(f,0,sizeof(f)),memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low));
    memset(head,0,sizeof(head)),cnt=ansn=tot=0,ans=-2;
    for(int i=1; i<=m; i++) scanf("%d%d",&x,&y),++x,++y,add(x,y),add(y,x);
    for(int i=1; i<=n; i++) if(!dfn[i]) rt=i,tarjin(i),ansn++;
    for(int i=1; i<=n; i++) ans=max(ans,f[i]);
    printf("%d\n",ans+ansn),scanf("%d%d",&n,&m);
  }
  return 0;
}

小結(jié)

沒啥好小結(jié)的，這系列題目都是以tarjin為基礎做些改動，重要是思路，其次是模板的背出來（熟練度）。不懂的地方，歡迎私信。

完結(jié)撒花?。?！
別忘了點贊，關(guān)注，謝謝！！