題面

1522
一句話題意：求割點(diǎn)數(shù)量。（夠短吧）

思路

模板題目。
首先，求割點(diǎn)數(shù)量需要用Tarjin（廢話），幾乎和求強(qiáng)連通分量一樣的代碼，只是需要加一個(gè)判斷。
一個(gè)點(diǎn)是割點(diǎn)的狀況有兩種：①是一個(gè)根，而且有不止一個(gè)子樹。②他的兒子節(jié)點(diǎn)（們）回溯不能回到dfn比他小的點(diǎn)上面去。
即：

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

所以求割點(diǎn)的代碼就長這樣：

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]);
}

我這里對每一個(gè)割點(diǎn)用vis數(shù)組表示，防止重算。
然后是輸入我要提一嘴。

 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;
}

小結(jié)

這道題就是求割點(diǎn)的模板，加上輸入、清空、判重……反正很簡單就是了，不多說，歡迎私信。

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