双连通分量 之 一本通 1525：电力

题面

1525
一句话题意：求一个图删除一个点之后，联通块最多有多少。（就是原题，没啥好精简的）

思路

删去了一个点之后，多的连通块个数相当于它的子树个数（就是dfn没更新过的那些点，不包括dfn更新过的点）。
注意：根节点增加的是子树个数减一，不然你会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;
}

最后的答案由两部分组成：①原有的连通块个数 ②删掉一个点，最多的增加量（最大的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;
}

小结

没啥好小结的，这系列题目都是以tarjin为基础做些改动，重要是思路，其次是模板的背出来（熟练度）。不懂的地方，欢迎私信。

完结撒花！！！
别忘了点赞，关注，谢谢！！