无序字母对

洛谷-P1341-无序字母对

实现

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

const int N = 60;
int n, g[N][N], deg[N];
vector<int> res;

int ch2i (char ch) {
    if ('A' <= ch && ch <= 'Z')
        return ch - 'A' + 1;
    return ch - 'a' + 27;
}
char i2ch (int x) {
    if (1 <= x && x <= 26)
        return x + 'A' - 1;
    return x + 'a' - 27;
}
void dfs (int cur) {
    for (int i = 1; i <= 52; ++ i) {
        if (g[cur][i] == 1) {
            g[cur][i] = g[i][cur] = 0;
            dfs(i);
        }
    }
    res.push_back(cur);
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        char a, b;
        cin >> a >> b;
        int u = ch2i(a), v = ch2i(b);
        g[u][v] = g[v][u] = 1;
        ++ deg[u], ++ deg[v];
    }

    int cnt = 0, v1 = 0, v2 = 0;
    for (int i = 1; i <= 52; ++ i) {
        if (deg[i] == 0) continue;
        if (deg[i] & 1) {
            ++ cnt;
            if (v1 == 0) v1 = i;
        } else {
            if (v2 == 0) v2 = i;
        }
    }
    if (cnt != 0 && cnt != 2) {
        cout << "No Solution" << endl;
    } else { // 存在欧拉回路或欧拉路
        cnt == 2 ? dfs(v1) : dfs(v2);
        reverse(res.begin(), res.end());
        for (int i = 0; i < res.size(); ++ i)
            cout << i2ch(res[i]);
    }
    return 0;
}