题解

思路分析

这是一道经典的 树的边双连通分量 + 贪心配对 问题。

问题建模

• 给定一棵 $n$ 个节点的树
• 需要添加最少的边使得删除任意一条边后图仍然连通
• 这等价于将树变成边双连通图

核心思路

1. 边双连通图的性质

边双连通图：删除任意一条边后图仍连通，即图中没有桥（割边）。

对于树：

• 所有边都是桥
• 需要添加边使得每条原有边都在至少一个环中

2. 叶子节点配对

关键观察：将叶子节点两两配对连边，可以消除最多的桥。

设树有 $L$ 个叶子节点，最少需要添加 $\lceil \frac{L}{2} \rceil$ 条边。

证明：

• 每条新边最多能覆盖两个叶子节点到其 LCA 的路径
• $L$ 个叶子需要至少 $\lceil \frac{L}{2} \rceil$ 条边

3. DFS 收集叶子

从根节点 DFS，按照 DFS 序收集所有叶子节点。

4. 贪心配对

将叶子按 DFS 序两两配对：

• 叶子 $[1, 2]$ 配对
• 叶子 $[3, 4]$ 配对
• ...
• 如果 $L$ 为奇数，叶子 $[\lceil \frac{L}{2} \rceil + 1, 1]$ 配对

算法步骤

1. 建树：读入边，建立邻接表

2. DFS 找叶子：

   • 从节点 1 开始 DFS
   • 记录所有度数为 1 的节点（叶子）

3. 配对输出：

   • 输出 $k = \lceil \frac{L}{2} \rceil$
   • 依次输出叶子对

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

#include <iostream>
#define MAXN 500003
using namespace std;

struct Edge
{
    int to, nxt;
} edges[MAXN << 1 | 1];
int cnt, head[MAXN], lf[MAXN];

inline void add_edge(const int &from, const int &to)
{
    edges[++cnt] = {to, head[from]}, head[from] = cnt;
}
void dfs(const int &u, const int &fa)
{
    if (!edges[head[u]].nxt)
        lf[++cnt] = u;
    for (int i = head[u], to; i; i = edges[i].nxt)
    {
        to = edges[i].to;
        if (to == fa)
            continue;
        dfs(to, u);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, u, v;
    cin >> n;
    for (int i = 1; i < n; ++i)
        cin >> u >> v, add_edge(u, v), add_edge(v, u);
    cnt = 0, dfs(1, 0);
    cout << ((cnt + 1) >> 1) << '\n';
    for (int i = 1; i <= ((cnt + 1) >> 1); ++i)
        cout << lf[i] << ' ' << lf[i + (cnt >> 1)] << '\n';
    return 0;
}

题解

原网络是一棵树，要让任意一条原有网线断开后仍保持连通，只需把所有叶子两两连成新的边，让每个叶子拥有不少于两条独立的出路。程序先用 DFS 遍历整棵树，借助 head 链表判断度数等于 1 的节点，将所有叶子按遍历顺序存入数组 lf。设叶子总数为 cnt，所需新边数即 ⌈cnt / 2⌉：把 lf 的前半段与后半段一一配对即可；当叶子数为奇数时，最后一个叶子与第一个叶子再连一条边。这样每个原来的叶子节点都多出一条冗余路径，整张图在删去任一原边后依旧连通。

#include <iostream>
#define MAXN 500003
using namespace std;

struct Edge
{
    int to, nxt;
} edges[MAXN << 1 | 1];
int cnt, head[MAXN], lf[MAXN];

inline void add_edge(const int &from, const int &to)
{
    edges[++cnt] = {to, head[from]}, head[from] = cnt;
}
void dfs(const int &u, const int &fa)
{
    if (!edges[head[u]].nxt)
        lf[++cnt] = u;
    for (int i = head[u], to; i; i = edges[i].nxt)
    {
        to = edges[i].to;
        if (to == fa)
            continue;
        dfs(to, u);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, u, v;
    cin >> n;
    for (int i = 1; i < n; ++i)
        cin >> u >> v, add_edge(u, v), add_edge(v, u);
    cnt = 0, dfs(1, 0);
    cout << ((cnt + 1) >> 1) << '\n';
    for (int i = 1; i <= ((cnt + 1) >> 1); ++i)
        cout << lf[i] << ' ' << lf[i + (cnt >> 1)] << '\n';
    return 0;
}