NC51307 Redundant Paths

题目：

• 给定无向连通图，求至少需要添加几条边使它变成一个边双连通图。
（添多少边可以消灭所有的桥）

题解：

先用边双连通缩点
• 缩点之后是一棵树
• 无根树的叶子（度数为1的点）都需要再添一条边，叶子节点两两连接
• 答案是是（叶子数+1）/2

在这里插入图片描述

代码：

这个题最坑的地方在于存在重边，我一直被卡。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
int n,m;
const int maxn=1e4+9;
vector<int>edge[maxn]; 
int low[maxn],dfn[maxn],vis[maxn];
int cnt=0;
int color[maxn],block=0;
stack<int>s;
int out[maxn];
int iff[maxn][maxn];
void tarjan(int u,int fa)
{
    low[u]=dfn[u]=++cnt;
    vis[u]=1;
    s.push(u);
    int b=0;
    for(int i=0;i<edge[u].size();i++)
    {

        int v=edge[u][i];
        if(v==fa&&!b){b=1;continue;}
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
    }
    int x;
    if(dfn[u]==low[u])
    {
        block++;
        do
        {
            x=s.top();
            s.pop();
            vis[x]=0;
            color[x]=block;
        }while(x!=u);
    } 
}
int lu[maxn],lv[maxn];
int main()
{
//    freopen("P2860_9.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        lu[i]=u;
        lv[i]=v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i,0);
    }
    int ans=0;

    for(int i=1;i<=m;i++)
        {
            int u=lu[i];
            int v=lv[i];
            int x=color[u];
            int y=color[v];
            if(x!=y)
            {
                out[y]++;
                out[x]++;
            }
        }
     for(int i=1;i<=block;i++)
     {
         if(out[i]==1)ans++;
    }
    //ans++;
     cout<<(ans+1)/2;
}