洛谷题单指南-连通性问题-P2860 [USACO06JAN] Redundant Paths G（边双连通分量）

原题链接：https://www.luogu.com.cn/problem/P2860

题意解读：在无向图中，最少需要加多少条边，使得整个图变成边双连通的，也就是不存在割边。

解题思路：

关于边双联通的概念和求法，请参考：https://www.cnblogs.com/hackerchef/p/18853318

对于本题，可以通过以下步骤解决：

1、找割边，找边双连通分量

2、根据边双联通分量对图进行缩点，形成树，所有边都是割边

3、要使得树变成双连通，任意两个节点之间至少有两条边，也就是一个节点至少有两条边，每个节点度数至少为2

4、统计所有度数为1的节点数量x，也就是叶子节点

5、最少需要将叶子节点两两相连，x时偶数时连x/2条边，x是奇数时还需要多连一条边x/2+1

6、综合一下，答案就是⌈x/2⌉，即(x+1)/2

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 5005, M = 20005;

int head[N], to[M], nxt[M], idx = 1; //idx从2开始
int dfn[N], low[N], timestamp;
stack<int> stk;
bool bridge[M]; //割边 
int ebcc[N], cnt; //节点的双联通分量编号
int degree[N]; //节点的度
int n, m;

void add(int a, int b)
{
    to[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

void tarjan(int u, int p)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);

    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == p) continue;
        if(!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);

            if(low[v] > dfn[u]) //找个割边
            {
                bridge[i] = bridge[i^1] = true; //i和i的反向边i^1都标记为割边
            }
        }
        else
        {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(low[u] == dfn[u])
    {
        cnt++;
        while(true)
        {
            int t = stk.top(); stk.pop();
            ebcc[t] = cnt;
            if(t == u) break;
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    //求割边，双连通分量
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i, 0);
    //不用真的缩点，只用计算缩点后每个点的度
    //由于是双向建边，只用枚举一遍所有割边，割边的终点对应的连通分量度数累加即可
    for(int i = 1; i <= idx; i++)
        if(bridge[i])
            degree[ebcc[to[i]]]++;

    int x = 0;
    for(int i = 1; i <= cnt; i++)
        if(degree[i] == 1) //统计度为1的节点数
            x++;
    cout << (x + 1) / 2;

    return 0;
}