「BZOJ 1718」Redundant Paths - 割边

给一个无向连通图，求至少加多少条边使得每两个点之间都存在至少两条路径，即使图没有割边。

链接

BZOJ 1718
POJ 3177

题解

求出边双连通分量后缩点，设叶子数量为 ，则答案为 。

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 5000;
const int MAXM = 10000;

struct Node
{
    struct Edge *firstEdge, *inEdge;
    int dfn, low, deg;
    bool vis;
    Node *fa;
} N[MAXN + 1];

struct Edge
{
    Node *from, *to;
    bool isCut;
    Edge *next, *revEdge;
                                      /* 不要忘记初始化 */
    Edge(Node *from, Node *to) : from(from), to(to), isCut(false), next(from->firstEdge) {}
} *E[MAXM + 1]; // 数组里存边的指针

inline Edge *addEdge(int from, int to)
{
    N[from].firstEdge = new Edge(&N[from], &N[to]);
    N[to].firstEdge = new Edge(&N[to], &N[from]);

    N[from].firstEdge->revEdge = N[to].firstEdge;
    N[to].firstEdge->revEdge = N[from].firstEdge;

    return N[from].firstEdge; // 返回一条边
}

int n, cnt;

inline void tarjan(Node *v)
{
    static int ts;
    v->dfn = v->low = ++ts;
    v->vis = true;

    for (Edge *e = v->firstEdge; e; e = e->next)
    {
        if (e->revEdge == v->inEdge) continue; // 判掉通过同一条边（互为反向边的两条有向边）走回去的情况

        if (!e->to->vis)
        {
            e->to->fa = v;
            e->to->inEdge = e;
            tarjan(e->to);

            v->low = std::min(v->low, e->to->low);

            if (e->to->low > v->dfn) // 注意没有等于，如果 e->to 通过其子节点的返祖边走到 v，e 就不是割边
            {                         // 或者当 v 和 e->to 之间有多条重边时，都不会是割边
                e->isCut = e->revEdge->isCut = true;
            }
        }
        else
        {
            v->low = std::min(v->low, e->to->dfn);
        }
    }
}


// 并查集
struct UFS
{
    int fa[MAXN + 1];

    void init(int n)
    {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }

    int find(int x)
    {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    void merge(int x, int y)
    {
        fa[find(x)] = find(y);
    }
} ufs;

int main()
{
    int m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);

        // 存储每一条 u 到 v 的边
        E[i] = addEdge(u, v);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!N[i].vis)
        {
            tarjan(&N[i]);
        }
    }

    ufs.init(n); // 并查集不要忘记初始化

    for (int i = 1; i <= m; i++)
    {
        // 并查集实现缩点，把非割边的两端点合并
        if (!E[i]->isCut) ufs.merge(E[i]->from - N, E[i]->to - N);
    }

    for (int i = 1; i <= m; i++) // 数组中只存了一个方向的边，不需处理正向反向边的问题
    {
        // 将割边加入到新图中，统计每个节点的度
        if (E[i]->isCut)
        {
            // printf("cutEdge: (%lu, %lu)\n", E[i]->from - N, E[i]->to - N);
            N[ufs.find(E[i]->from - N)].deg++;
            N[ufs.find(E[i]->to - N)].deg++;
        }
    }

    int leaves = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ufs.find(i) == i) // 枚举每个连通块（用并查集中的每个根节点代表每个连通块，即每个边双连通分量）
        {
            if (N[i].deg == 1) // 统计叶子节点的数量
            {
                leaves++;
            }
        }
    }

    // printf("leaves = %d\n", leaves);
    printf("%d\n", (leaves + 1) / 2);

    return 0;
}