Redundant Paths POJ - 3177（边双连通分量&&缩点）

题目链接

Redundant Paths POJ - 3177

题意

有F个牧场，1<=F<=5000，现在一个牧群经常需要从一个牧场迁移到另一个牧场。奶牛们已经厌烦老是走同一条路，所以有必要再新修几条路，这样它们从一个牧场迁移到另一个牧场时总是可以选择至少两条独立的路。现在F个牧场的任何两个牧场之间已经至少有一条路了，奶牛们需要至少有两条。
给定现有的R条直接连接两个牧场的路，F-1<=R<=10000，计算至少需要新修多少条直接连接两个牧场的路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指没有公共边的路，但可以经过同一个中间顶点。

分析

抽象成图论模型：给定一个连通图，求至少加多少条边使得这个图是一个边双连通图。
求出边双连通分量，将每个边双连通分量缩成一个点，这样原图就变成一个树图。我们只要找到所有在树图中度数为1的点，将其两两连边，使得每个点的度数都大于等于2即可。
求边双连通分量用tarjan算法，时间复杂度为O（n+m）。找度数为1的点的时间复杂度为O（n+m）。所以总时间复杂度为O（n+m）。

需要注意的是题干未说明没有重边，所以在建图的时候需要自己去掉重边。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;

const int maxn=5e3+100;
vector<int> g[maxn];
int n,m,par[maxn],du[maxn];
int dfn[maxn],low[maxn];
stack<int> sta;
bool map[maxn][maxn];

void tarjan(int u,int fa,int dep)
{
    dfn[u]=low[u]=dep;
    sta.push(u);
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==fa) continue;
        if(dfn[v])
            low[u]=min(low[u],dfn[v]);
        else
        {
            tarjan(v,u,dep+1);
            low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        while(!sta.empty())
        {
            int tmp=sta.top();sta.pop();
            par[tmp]=u;
            if(tmp==u) break;
        }
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            int x=par[i];
            int y=par[g[i][j]];
            if(x!=y)
                du[x]++;
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
        if(du[i]==1)
        sum++;
    printf("%d\n",(sum+1)/2);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(du,0,sizeof(du));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(map,false,sizeof(map));
        for(int i=0;i<=n;i++) par[i]=i;
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(!map[u][v])//注意重边
            {
                g[u].push_back(v);
                g[v].push_back(u);
                map[u][v]=map[v][u]=true;
            }

        }
        tarjan(1,-1,1);
        solve();
        for(int i=0;i<=n;i++) g[i].clear();
    }
    return 0;
}