洛谷2860 冗余路径Redundant Paths

题意

给一个无向图，要求任意两个点之间都至少有两条相离的路径，求最少的连边数。

其中点数 $N\le 5000$ ，边数 $M\le 10000$ 。

题解

显然环上的节点都满足这个要求，所以题目可以理解成要求所有节点都在环上，那么可以先把已经有的环缩点。

缩完点后就变成了一棵树，要让所有点在环上，那么把所有叶子节点之间两两连接即可。当然叶子节点也有可能有奇数个，所以需要连边的个数为 $(leaf+1)\div 2$ 。

至于找叶子节点，可以遍历每条不重复的边，对两端节点记录度数，最后度数为 $1$ 就是叶子。对于重边可以记录所有单向边，排序后进行去重。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int from,next,to;
} edge[20005],edge2[20005];
stack <int> s;
int cnt,head[5005],cnt2,head2[5005],n,m,a,b,deg[5005];
int id[5005],low[5005],scc[5005],dfsord,scnt;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].from=u;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void add2(int u,int v)
{
    edge2[++cnt2].to=v;
    edge2[cnt2].from=u;
    edge2[cnt2].next=head2[u];
    head2[u]=cnt2;
}

void dfs(int x,int f)
{
    id[x]=low[x]=++dfsord;
    s.push(x);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        if (!id[y])
        {
            dfs(y,x);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            if (t==x) break;
        }
    }
}

inline bool cmp(Edge x,Edge y) { return (x.from==y.from) ? x.to<y.to : x.from<y.from; }

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
        add2(a,b);
    }
    for (int i=1;i<=n;i++)
    {
        if (id[i]) continue;
        dfs(i,0);
    }
    sort(edge2+1,edge2+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
        int x=edge2[i].from,y=edge2[i].to;
        if (x==edge2[i-1].from && y==edge2[i-1].to) continue;
        if (scc[x]==scc[y]) continue;
        deg[scc[x]]++;
        deg[scc[y]]++;
    }
    int ans=0;
    for (int i=1;i<=scnt;i++) ans+=(deg[i]==1);
    return !printf("%d",(ans+1)>>1);
}