euler tour (by pure theory), C++ (gcc)

euler tour (by pure theory)

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

map<string, int> m;
map<int, string> inv;
int total = 1;

void build(){
    vector<char> v;
    for(int j = 0; j < 10; j++) v.pb((char)(j + '0'));
    for(int j = 0; j < 26; j++) v.pb((char)(j + 'a'));
    for(int j = 0; j < 26; j++) v.pb((char)(j + 'A'));
    
    int n = v.size();
    int& ind = total;
    for(int j = 0; j < n; j++){
        for(int k = 0; k < n; k++){
            string cur = "";
            cur += v[j];
            cur += v[k];
            m[cur] = ind;
            inv[ind++] = cur;
        }
    }
    ind --;
}

vector< vector<int> > g;

void dfs(int s, vector<int>& ans, vector<int>& ind){
    ans.pb(s);
    if(ind[s] == g[s].size()) return;
    ind[s] ++;
    dfs(g[s][ind[s] - 1], ans, ind);
}

struct node{
    vector<int> v;
    int ind;
    
    node(vector<int> x) : v(x), ind(0){}
};

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    build();
    g.resize(total+1);
    
    int n, st = -1;
    cin >> n;
    for(int j = 0; j < n; j++){
        string x;
        cin >> x;
        string fr = "";
        fr += x[0];
        fr += x[1];
        string sc = "";
        sc += x[1];
        sc += x[2];
        g[m[fr]].pb(m[sc]);
        
        st = m[fr];
    }
    
    // find a euler path
    // check the in and out degree (as directed graph)
    vector<int> in(total+1, 0), out(total+1, 0);
    for(int j = 1; j <= total; j++){
        out[j] = g[j].size();
        for(auto i : g[j]) in[i]++;
    }
    int diff_more_than_1 = 0;
    vector<int> in_less, out_less;
    for(int j = 1; j <= total; j++){
        if(in[j] == out[j]) continue;
        
        if(abs(in[j] - out[j]) > 1){
            diff_more_than_1 = 1;
            break;
        }
        if(in[j] > out[j]) out_less.pb(j);
        else in_less.pb(j);
    }
    if(in_less.size() > 1 || out_less.size() > 1 || diff_more_than_1 || in_less.size() != out_less.size()){
        cout << "NO";
        return 0;
    }
    if((int)in_less.size() == 1){
        // add an extra edge to complete the Euler circuit
        g[out_less[0]].pb(in_less[0]);
    }
    vector<int> ind(total+1, 0);
    vector<int> cycle, ans;
    dfs(st, cycle, ind);
    
    //for(auto i : cycle) cout << inv[i] << " "; cout << endl;
    
    stack<node> s;
    s.push(node(cycle));
    while(!s.empty()){
        cycle.clear();
        int cur = s.top().v[s.top().ind++];
        if(g[cur].size() != ind[cur]){
            dfs(cur, cycle, ind);            
            s.push(node(cycle));
        }
        else ans.pb(cur);
        
        while(!s.empty() && s.top().ind == s.top().v.size()) s.pop();
    }
    ans.pop_back();
    int edges = n + in_less.size();
    if(ans.size() != edges){
        cout << "NO";
        return 0;
    }
    // if we had added the edge then it's the time to remove it
    if((int)in_less.size() == 1){
        int from = out_less[0], to = in_less[0];
        //cout << from << " " << to << endl;
        for(int j = 1; j < ans.size(); j++)
            if(ans[j-1] == from && ans[j] == to){
                vector<int> tmp = ans;
                ans.clear();
                for(int i = j; i < (int)tmp.size(); i++) ans.pb(tmp[i]);
                for(int i = 0; i < j; i++) ans.pb(tmp[i]);
                break;
            }
    }
    if(in_less.size() == 0) ans.pb(ans[0]);
    string result = "";
    for(auto i : ans) result += inv[i][0];
    result += inv[ans.back()][1];
    
    cout << "YES\n";
    cout << result << endl;
    return 0;
}


run \| edit \| history \| help	0