双连通分量 之 一本通1522：网络

题面

1522
一句话题意：求割点数量。（够短吧）

思路

模板题目。
首先，求割点数量需要用Tarjin（废话），几乎和求强连通分量一样的代码，只是需要加一个判断。
一个点是割点的状况有两种：①是一个根，而且有不止一个子树。②他的儿子节点（们）回溯不能回到dfn比他小的点上面去。
即：

(rt==k&&cntt>1)||(rt!=k&&low[a[i].to]>=dfn[k])

所以求割点的代码就长这样：

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

我这里对每一个割点用vis数组表示，防止重算。
然后是输入我要提一嘴。

 scanf("%d",&x);
 while(x)
    {
      while(getchar()!='\n') scanf("%d",&y),add(x,y),add(y,x);
      scanf("%d",&x);
    }

我这里用了getchar来查换行。

代码

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

小结

这道题就是求割点的模板，加上输入、清空、判重……反正很简单就是了，不多说，欢迎私信。

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