欧拉路径

无向图

有向图

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <utility> // For std::pair

// 使用 using namespace std; 在竞赛中常见，但大型项目中不推荐
using namespace std;

// 常量定义
const int MAX_CHAR_VAL = 64; // 字符编码后的最大值 (0-63)
const int MAX_NODE_IDX = MAX_CHAR_VAL * 100 + MAX_CHAR_VAL + 1; // 节点索引最大值 + 1

// 将字符映射到整数 (a-z: 0-25, A-Z: 26-51, 0-9: 52-61)
// 你的原函数 f 映射到 0-25, 27-52, 54-63。为了简化，我们用连续的范围
int ctoi(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 26;
    if (c >= '0' && c <= '9') return c - '0' + 52;
    return -1; //  表示无效字符，尽管题目可能保证输入有效
}

// 将整数映射回字符
char itoc(int x) {
    if (x >= 0 && x < 26) return 'a' + x;
    if (x >= 26 && x < 52) return 'A' + (x - 26);
    if (x >= 52 && x < 62) return '0' + (x - 52); // 0-9 是10个字符
    return '?'; // 表示无效编码
}

// 节点用 pair<int, int> 表示其两个字符的编码
using Node = pair<int, int>;

// 邻接表，存储从当前节点出发可以到达的目标节点（也是 pair<int, int>）
// 原代码中 deque<node2> edge[114514]; node2 中的 vis 未使用，故简化
deque<Node> adj[MAX_NODE_IDX];

// 存储欧拉路径/回路的结果
stack<Node> path_stack;

// 度数信息
int in_deg[MAX_NODE_IDX];  // 入度
int out_deg[MAX_NODE_IDX]; // 出度
// p 数组在原代码中用于记录 out_deg - in_deg，这里可以用 bal (balance) 代替
int balance[MAX_NODE_IDX];

// Hierholzer 算法的 DFS 部分
// c1, c2 代表当前节点的两个字符编码
void find_euler_path(int c1, int c2) {
    int u_idx = c1 * 100 + c2; // 当前节点的整数表示

    // 遍历当前节点的所有出边
    // 注意：这里修改了循环方式，原代码的 for + pop_front 有风险且低效
    while (!adj[u_idx].empty()) {
        Node next_node_comps = adj[u_idx].front();
        adj[u_idx].pop_front(); // 取出并删除边，标记为已访问

        find_euler_path(next_node_comps.first, next_node_comps.second);
    }
    // 当一个节点的所有出边都被访问后，将该节点入栈
    path_stack.push({c1, c2});
}

int main() {
    // 竞赛中加速IO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 输入的三字符序列数量
    cin >> n;

    if (n == 0) { // 特殊情况：没有边
        cout << "YES\n\n"; // 或者只打印 YES 根据题目要求
        return 0;
    }

    // 用于记录图中实际出现的第一个节点，作为欧拉回路的备选起点
    Node first_graph_node = {-1, -1};

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s; // 读取三个字符的字符串 "abc"
        char char_a = s[0];
        char char_b = s[1];
        char char_c = s[2];

        int code1 = ctoi(char_a);
        int code2 = ctoi(char_b);
        int code3 = ctoi(char_c);

        // 节点 u: (code1, code2), 节点 v: (code2, code3)
        // 边: u -> v
        int u_idx = code1 * 100 + code2;
        int v_idx = code2 * 100 + code3;

        out_deg[u_idx]++;
        in_deg[v_idx]++;
        adj[u_idx].push_back({code2, code3}); // 存储目标节点的组成字符

        if (first_graph_node.first == -1) {
            first_graph_node = {code1, code2};
        }
    }

    Node start_node = {-1, -1}; // DFS的起始节点
    int start_candidates = 0;   // 潜在路径起点数量 (out_deg - in_deg == 1)
    int end_candidates = 0;     // 潜在路径终点数量 (in_deg - out_deg == 1)
    bool possible = true;

    // 遍历所有可能的节点编码，检查度数条件
    // 字符编码最大为 ctoi() 返回的最大值，比如 61
    // 节点由两个字符编码组成
    for (int c1_code = 0; c1_code < MAX_CHAR_VAL; ++c1_code) {
        for (int c2_code = 0; c2_code < MAX_CHAR_VAL; ++c2_code) {
            int current_node_idx = c1_code * 100 + c2_code;

            // 只考虑在图中实际存在的节点 (至少有一条出边或入边)
            if (out_deg[current_node_idx] == 0 && in_deg[current_node_idx] == 0) {
                continue;
            }
            
            // 更新 balance 数组
            balance[current_node_idx] = out_deg[current_node_idx] - in_deg[current_node_idx];

            if (balance[current_node_idx] == 1) { // 欧拉路径的起点
                start_candidates++;
                start_node = {c1_code, c2_code};
            } else if (balance[current_node_idx] == -1) { // 欧拉路径的终点
                end_candidates++;
            } else if (balance[current_node_idx] != 0) { // 度数不平衡，且不是起点/终点
                possible = false;
                break;
            }
            // 如果是欧拉回路 (balance == 0)，且还没有设置起点，
            // 并且该节点有出度，则可以作为回路的起点
            if (start_node.first == -1 && out_deg[current_node_idx] > 0) {
                 // 这一步是为了确保如果图是欧拉回路，我们有一个起点
                 // first_graph_node 在读输入时已经记录了第一个遇到的 (有出度的) 节点，更可靠
            }
        }
        if (!possible) break;
    }

    if (!possible) {
        cout << "NO\n";
        return 0;
    }

    // 判断欧拉路径/回路的条件
    if (start_candidates == 0 && end_candidates == 0) {
        // 可能是欧拉回路，或者图中没有满足条件的路径起点/终点
        // 如果是欧拉回路，从图中任意一个有出度的节点开始
        // first_graph_node 记录了第一个遇到的 (c1,c2) 节点，可以作为回路起点
        if (first_graph_node.first != -1) { // 确保图不是空的
             start_node = first_graph_node;
        } else if (n > 0) { // 有边但找不到任何有效节点（理论上不应发生，除非图是空的或 ctoi 映射问题）
            cout << "NO\n";
            return 0;
        }
        // 如果 n=0，已在开头处理
    } else if (start_candidates == 1 && end_candidates == 1) {
        // 确定是欧拉路径，start_node 已经被设为起点
    } else {
        // 不满足欧拉路径或回路的度数条件
        cout << "NO\n";
        return 0;
    }

    // 如果有边输入 (n > 0)，但没有找到合适的起点 (例如图不连通或度数条件不满足)
    if (n > 0 && start_node.first == -1) {
        cout << "NO\n";
        return 0;
    }
    
    // 对于 n>0 的情况，此时 start_node 必须有效
    if (start_node.first != -1) { // 只有当图非空且找到起点时才DFS
        find_euler_path(start_node.first, start_node.second);
    }


    // 检查结果：路径中节点数应为边数 + 1
    if (path_stack.size() == n + 1) {
        cout << "YES\n";
        // 输出路径
        // 第一个节点 (c1, c2) 输出 c1c2
        // 后续节点 (cx, cy) 只输出 cy
        Node current = path_stack.top();
        path_stack.pop();
        cout << itoc(current.first) << itoc(current.second);

        while (!path_stack.empty()) {
            current = path_stack.top();
            path_stack.pop();
            cout << itoc(current.second); // 只输出第二个字符
        }
        cout << "\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}