我的算法书 - 无序字母对

这道题是 欧拉路 (Euler Path) 的经典应用。

简而言之：把字母看作“点”，把给定的字母对看作“边”。题目就是要求一笔画走完所有边。

核心解题逻辑

1 建模 (Mapping)

节点：ASCII 字符（‘A’-‘Z’, ‘a’-‘z’）。
边：输入的两个字母之间连一条无向边。
目标：找一条路径，经过每条边恰好一次（欧拉路/欧拉回路）。

2 判别条件 (Existence)

图必须连通，且满足度数要求：

欧拉回路（起点回到起点）：所有点的度数都是偶数。
欧拉路（起点终点不同）：只有 2个点的度数是奇数，其余全为偶数。
无解：奇数度点的个数不是 0 也不是 2，或者图不连通。

3 字典序最小 (Lexicographical Order)

题目要求字典序最小，包含两层含义：

1 起点选择：

如果有奇点，必须从ASCII码较小的那个奇点出发。
如果是回路（全偶点），从ASCII码最小的有边节点出发。

2 路径选择：

在 DFS 过程中，优先走 ASCII 码小的邻居（使用邻接矩阵枚举即可自然满足）。

4 算法流程 (Hierholzer’s Algorithm 变体)

DFS 遍历：每走过一条边，就删除这条边（防止走回头路）。
入栈时机：回溯时记录节点（当一个点没有路可走时，将其加入栈/结果集）。
为什么？ 因为DFS会先钻到底，最后回溯的顺序才是正确的拼接顺序（逆序）。
输出：将记录的节点倒序输出。

代码实现

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

        #include <iostream>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

// 邻接矩阵存图，G[u][v]=1 表示有边，自动满足字典序遍历
int G[150][150]; 
int du[150]; // 记录度数
stack<char> st; // 存路径
int n; // 边数

// 核心 DFS：Hierholzer 算法
void dfs(int u) {
    // 按 ASCII 顺序从小到大遍历邻居
    for (int v = 0; v < 150; v++) {
        if (G[u][v]) {
            G[u][v]--; // 删边 (无向图删两边)
            G[v][u]--;
            dfs(v); // 递归
        }
    }
    st.push(u); // 【关键】无路可走时入栈
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        G[s[0]][s[1]] = G[s[1]][s[0]] = 1; // 建边
        du[s[0]]++; du[s[1]]++; // 统计度数
    }

    int start_node = 0;
    int odd_count = 0;
    
    // 1. 找起点 & 检查度数
    for (int i = 0; i < 150; i++) {
        if (du[i] % 2 != 0) odd_count++;
    }

    if (odd_count != 0 && odd_count != 2) {
        cout << "No Solution";
        return 0;
    }

    // 确定起点：
    // 如果有奇点，找最小的奇点；
    // 如果全偶，找最小的有度数的点。
    for (int i = 0; i < 150; i++) {
        if (du[i]) { // 这是一个存在的点
            if (odd_count == 2) {
                if (du[i] % 2 != 0) {
                    start_node = i;
                    break;
                }
            } else { // odd_count == 0
                start_node = i;
                break;
            }
        }
    }
    // std::cout << odd_count << "\n";
    // std::cout << "start_node  "<< "\n";
    // std::cout << (char)start_node << "\n";

    // 2. 开始搜索
    dfs(start_node);

    // 3. 检查连通性 (防止图不连通的情况)
    // 欧拉路径的点数应该是 边数 + 1
    if (st.size() != n + 1) {
        cout << "No Solution";
        return 0;
    }

    // 4. 输出
    while (!st.empty()) {
        cout << (char)st.top();
        st.pop();
    }

    return 0;
}

但是这个代码M L E了

问题出在 dfs 函数中删除边的逻辑上。

题目中提到“无序字母对”，并没有明确禁止自环（即两个字母相同，如 AA）。虽然题目说“各不相同的无序字母对”，但通常测试数据中可能会包含 AA 这样的合法输入（或者即使没有，代码逻辑也应严谨）。

看看上面的代码：

cpp

copy

        1
2
3
4
5
6

        if (G[u][v]) {
    G[u][v]--; // 第一步：减 1
    G[v][u]--; // 第二步：再减 1
    dfs(v); 
}

假设输入中有一个自环 X X：

建图时：G[‘X’][‘X’] = 1。
进入 dfs(‘X’)，遍历到 v = ‘X’。
G[‘X’][‘X’] 是 1，进入 if。
G[‘X’][‘X’]–，此时值变为 0。
G[‘v’][‘u’]-- （因为 $u=v$ ，还是操作同一个位置），此时值变为 -1。
递归调用 dfs(‘X’)。在下一层递归中，检查 if (G[‘X’][‘X’])。
在 C++ 中，非 0 值（包括 -1）都为真。
条件成立，继续递归，值变为 -2, -3… 导致无限递归，最终爆栈。

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

        #include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

int G[150][150]; 
int du[150]; 
stack<char> st; 
int n; 

void dfs(int u) {
    for (int v = 0; v < 150; v++) {
        // 这里必须判断 G[u][v] > 0，防止逻辑错误访问到负数（虽然改了删边逻辑后一般不会）
        if (G[u][v] > 0) {
            G[u][v]--; 
            // 【修复点】如果是自环(u==v)，只减一次；否则两边都减
            if (u != v) G[v][u]--; 
            
            dfs(v); 
        }
    }
    st.push(u); 
}

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        int u = s[0];
        int v = s[1];
        // 建议使用 ++ 支持多重图（尽管本题说各不相同，这样写更稳健）
        G[u][v]++; 
        if (u != v) G[v][u]++; 
        
        du[u]++; 
        du[v]++; 
    }

    int start_node = 0;
    int odd_count = 0;
    
    // 寻找奇点
    for (int i = 0; i < 150; i++) {
        if (du[i] % 2 != 0) odd_count++;
    }

    // 欧拉路径存在条件：奇点数为 0 或 2
    if (odd_count != 0 && odd_count != 2) {
        cout << "No Solution";
        return 0;
    }

    // 确定起点
    // 策略：
    // 1. 如果有奇点，起点必须是奇点中 ASCII 较小的那个。
    // 2. 如果全是偶点，起点是所有有度数的点中 ASCII 最小的。
    for (int i = 0; i < 150; i++) {
        if (du[i] > 0) { // 必须是图中的点
            if (odd_count == 2) {
                if (du[i] % 2 != 0) {
                    start_node = i;
                    break; // 找到第一个奇点就是最小的（因为从小到大遍历）
                }
            } else { // odd_count == 0
                start_node = i;
                break; // 找到第一个有点就是最小的
            }
        }
    }

    dfs(start_node);

    // 检查是否走完了所有的边 (路径点数 = 边数 + 1)
    if (st.size() != n + 1) {
        cout << "No Solution";
        return 0;
    }

    while (!st.empty()) {
        cout << (char)st.top();
        st.pop();
    }

    return 0;
}

记忆要点

1 奇点数：必须是 0 或 2。 2 删边：DFS 走过就拆桥。 3 回溯入栈：走到死胡同再记录，最后倒序输出。 4 贪心：邻居从小到大找。

目录

核心解题逻辑

1 建模 (Mapping)

2 判别条件 (Existence)

3 字典序最小 (Lexicographical Order)

4 算法流程 (Hierholzer’s Algorithm 变体)

代码实现

记忆要点