题面

1520：【例 1】分离的路径
一句话题意：求无向图中，加多少条边成为双连通分量（无桥）。

思路

先用Tarjin求边双连通分量，再缩点，统计叶子节点ans，答案为(ans+1)/2
具体这个答案的分析请看我的另一篇文章。
首先是Tarjin求边双连通分量，求法也请看我的另一篇文章。这里就直接上代码，十分模板，十分基础，十分简单……

stack<int> st;
void tarjin(int k)
{
  dfn[k]=low[k]=++tot,st.push(k);
  for(int i=head[k]; i; i=a[i].nxt)
    if(!vis[a[i].p])
    {
      vis[i]=1;
      if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
      else low[k]=min(low[k],low[a[i].to]);
    }
    else vis[i]=1;
  if(low[k]==dfn[k])
  {
    co[k]=++num;
    while(st.top()!=k) co[st.top()]=num,st.pop();
    st.pop();
  }
}

然后是统计叶子节点，即统计入度/出度为1的点，也很简单，注意不要重复统计。

for(int i=1; i<=n; i++)
    for(int j=head[i]; j; j=a[j].nxt)
      if(vis[a[j].p])
      {
        vis[j]=0;
        if(co[a[j].to]!=co[i]) in[co[a[j].to]]++,in[co[i]]++;
      }
      else vis[j]=0;//统计入度
  for(int i=1; i<=num; i++) if(in[i]==1) ans++;  //叶子节点

最后就是输出，答案是 。

代码

直接上代码，不多说。

#include <bits/stdc++.h>
using namespace std;
int co[10005],dfn[10005],low[10005],num,tot;
int cnt,head[5005];
bool vis[5005];
int n,m,x,y,in[5005],ans;
struct node
{
  int to,nxt,p;
} a[20005];
void add(int x,int y)
{
  a[++cnt].to=y,a[cnt].nxt=head[x],a[cnt].p=cnt+1,head[x]=cnt;
  a[++cnt].to=x,a[cnt].nxt=head[y],a[cnt].p=cnt-1,head[y]=cnt;
}//两次连边
stack<int> st;
void tarjin(int k)
{
  dfn[k]=low[k]=++tot,st.push(k);
  for(int i=head[k]; i; i=a[i].nxt)
    if(!vis[a[i].p])
    {
      vis[i]=1;
      if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
      else low[k]=min(low[k],low[a[i].to]);
    }
    else vis[i]=1;
  if(low[k]==dfn[k])
  {
    co[k]=++num;
    while(st.top()!=k) co[st.top()]=num,st.pop();
    st.pop();
  }
}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1; i<=m; i++) scanf("%d%d",&x,&y),add(x,y);
  tarjin(1);//1为根
  for(int i=1; i<=n; i++)
    for(int j=head[i]; j; j=a[j].nxt)
      if(vis[a[j].p])
      {
        vis[j]=0;
        if(co[a[j].to]!=co[i]) in[co[a[j].to]]++,in[co[i]]++;
      }
      else vis[j]=0;//统计入度
  for(int i=1; i<=num; i++) if(in[i]==1) ans++;  //叶子节点
  printf("%d\n",(ans+1)/2);
  return 0;
}

小结

关于思路，十分简单的tarjin缩点，求叶子，再套公式（找规律），这个公式还是比较有用的。
关于细节，注意不要重复计算，所以我这里做了一个a[i].p，作为反向边，防止重数。
还有问题请私信我。

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