「ROI 2021 Day2」树上配对 题解

题目理解

我们有一个由树构建的有向图：原树的每条无向边被替换为两条方向相反的边。现在删除了若干对边，需要将剩余的边配对。

配对定义：两条边 $(u,v)$ 和 $(v,w)$ 可以配对，当且仅当第一条边的终点等于第二条边的起点。特别地，两条反向边 $(u,v)$ 和 $(v,u)$ 可以配对。

关键观察

1. 度数条件

对于每个顶点 $v$：

• 每条进入 $v$ 的边 $(u,v)$ 必须与一条离开 $v$ 的边 $(v,w)$ 配对
• 因此，每个顶点的入度必须等于出度

这是问题有解的必要条件。

2. 图的结构特性

由于原图是从树构建的：

• 删除边后，图可能不再连通
• 但每个连通分量必须满足度数条件
• 配对实际上是在寻找图的欧拉回路分解

3. 配对构造

可以将问题转化为：将图分解为若干个边不相交的环，每个环对应一系列配对。

算法思路

方法：基于度数检查和DFS的配对构造

步骤1：度数检查

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> in_deg(n + 1, 0), out_deg(n + 1, 0);
    vector<vector<pair<int, int>>> adj(n + 1); // 邻接表：存储(邻居, 边编号)
    vector<pair<int, int>> edges; // 存储所有边
    
    // 读取输入并计算度数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
        adj[u].push_back({v, i});
        out_deg[u]++;
        in_deg[v]++;
    }
    
    // 检查必要条件：每个顶点入度=出度
    for (int i = 1; i <= n; i++) {
        if (in_deg[i] != out_deg[i]) {
            cout << "No" << endl;
            return 0;
        }
    }

步骤2：DFS寻找配对

    vector<bool> used(m, false); // 标记边是否已使用
    vector<vector<int>> pairs; // 存储配对结果
    
    for (int i = 0; i < m; i++) {
        if (used[i]) continue;
        
        // 从当前边开始寻找配对链
        int current = i;
        vector<int> path;
        
        while (!used[current]) {
            used[current] = true;
            path.push_back(current);
            
            auto [u, v] = edges[current];
            
            // 寻找下一条边：从v出发的未使用边
            bool found = false;
            for (auto [w, idx] : adj[v]) {
                if (!used[idx]) {
                    current = idx;
                    found = true;
                    break;
                }
            }
            
            if (!found) break;
        }
        
        // 将路径分解为配对
        for (int j = 0; j < path.size(); j += 2) {
            if (j + 1 < path.size()) {
                int e1 = path[j], e2 = path[j + 1];
                pairs.push_back({edges[e1].first, edges[e1].second, 
                               edges[e2].first, edges[e2].second});
            }
        }
    }

步骤3：输出结果

    cout << "Yes" << endl;
    for (auto& p : pairs) {
        cout << p[0] << " " << p[1] << " " << p[2] << " " << p[3] << endl;
    }
    
    return 0;
}

完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> in_deg(n + 1, 0), out_deg(n + 1, 0);
    vector<vector<pair<int, int>>> adj(n + 1);
    vector<pair<int, int>> edges;
    
    // 读取输入
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
        adj[u].push_back({v, i});
        out_deg[u]++;
        in_deg[v]++;
    }
    
    // 检查度数条件
    for (int i = 1; i <= n; i++) {
        if (in_deg[i] != out_deg[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    vector<bool> used(m, false);
    vector<vector<int>> pairs;
    
    // 尝试为每条未使用的边寻找配对
    for (int i = 0; i < m; i++) {
        if (used[i]) continue;
        
        // 使用栈模拟DFS，避免递归深度过大
        vector<int> path;
        int current = i;
        
        while (true) {
            used[current] = true;
            path.push_back(current);
            
            auto [u, v] = edges[current];
            
            // 寻找从v出发的未使用边
            bool found = false;
            while (!adj[v].empty()) {
                auto [w, idx] = adj[v].back();
                adj[v].pop_back();
                if (!used[idx]) {
                    current = idx;
                    found = true;
                    break;
                }
            }
            
            if (!found) break;
        }
        
        // 将路径分解为配对
        for (int j = 0; j + 1 < path.size(); j += 2) {
            int e1 = path[j], e2 = path[j + 1];
            pairs.push_back({
                edges[e1].first, edges[e1].second,
                edges[e2].first, edges[e2].second
            });
        }
    }
    
    // 检查是否所有边都被配对
    if (pairs.size() * 2 != m) {
        cout << "No" << endl;
        return 0;
    }
    
    cout << "Yes" << endl;
    for (auto& p : pairs) {
        cout << p[0] << " " << p[1] << " " << p[2] << " " << p[3] << endl;
    }
    
    return 0;
}

算法正确性证明

1. 必要性证明

如果存在配对，则对于每个顶点 $v$：

• 每条进入 $v$ 的边必须与一条离开 $v$ 的边配对
• 因此 $in\_deg(v) = out\_deg(v)$

2. 充分性证明

当度数条件满足时，图可以分解为若干欧拉回路。在每个回路中，我们可以将相邻的边两两配对。

3. 构造正确性

算法通过DFS寻找路径，确保：

• 每条边只被使用一次
• 配对满足定义：$e_1$ 的终点 = $e_2$ 的起点

复杂度分析

• 时间复杂度：$O(n + m)$
  • 度数检查：$O(n)$
  • DFS遍历：$O(m)$
• 空间复杂度：$O(n + m)$

样例验证

样例1

输入：
5 6
1 2
2 1
1 5
2 3
2 4
4 2

处理：
- 检查度数：所有顶点入度=出度
- 找到配对：
  (1,2) + (2,3)
  (2,1) + (1,5)  
  (2,4) + (4,2)

样例2

输入：
4 4
2 1
2 3
2 4
4 2

处理：
- 顶点2：入度=1，出度=3 → 不相等
- 输出"No"

样例3

输入：
4 4
1 2
2 1
3 4
4 3

处理：
- 度数条件满足
- 找到配对：
  (1,2) + (2,1)
  (3,4) + (4,3)

优化技巧

1. 使用栈而非递归：避免DFS递归深度过大
2. 及时删除已处理边：从邻接表中弹出已使用边，减少后续查找时间
3. 批量处理：一次处理一个连通分量

总结

本题的关键在于：

1. 发现度数平衡的必要条件
2. 将配对问题转化为欧拉回路分解
3. 使用DFS高效构造配对方案

这种"度数检查 + 路径分解"的方法能够有效解决此类边配对问题。