Implementation

class Graph {
public:
    Graph(const vector<pair<string, string>> &connections) {
        // good metric for reservation, consider the worse case:
        // A->B; C->D; D->E; E->F == size == 4, but has 8 graph members
        g.reserve(connections.size() + connections.size() *.5);
        process_connections(connections);
    }

    Graph(unordered_map<string, unordered_set<string>> &graph) : g(graph) {}

    unordered_map<string, unordered_set<string>> g;
private:

    // handles user defined redundent connections
    void process_connections(const vector<pair<string, string>> &data) {
        for (auto &p : data) {
            if (g.find(p.first) == g.end())
                g.insert({ p.first, unordered_set<string>() });
            if (g.find(p.second) == g.end())
                g.insert({ p.second, unordered_set<string>() });
        }

        for (auto &p : data) {
            g[p.first].insert(p.second);
            g[p.second].insert(p.first);
        }
    }
};

class EularianCycle {
public:
    EularianCycle(Graph g) : g(g.g), restore(g.g) {
        if (!isEularian(g)) {
            cout << "Graph does not contain eularian cycle" << endl;
        }
    }

    vector<string> Hierholzers_iterative(const string &start) {
        vector<string> final_path;
        if (!isEularian(this->g)) return final_path;
        stack<string> temp_path;
        temp_path.push(start);

        while (!temp_path.empty()) {
            string top = temp_path.top();

            if (!g[top].empty()) {
                string rand_elm = *g[top].begin();
                temp_path.push(rand_elm);

                // delete both
                // A -> B implies B -> A
                g[top].erase(rand_elm);
                g[rand_elm].erase(top);
            }
            else {
                final_path.push_back(top);
                temp_path.pop();
            }
        }

        g = restore;
        return vector<string>(final_path.rbegin(), final_path.rend());
    }

    vector<string> Hierholzers_recursive(const string &start) {
        vector<string> final_path;
        if (!isEularian(this->g)) return final_path;
        _Hierholzers_recursive(start, final_path); 
        g = restore;
        return vector<string>(final_path.rbegin(), final_path.rend());
    }

private:
    using graph = unordered_map<string, unordered_set<string>>;
    graph g, restore;

    void _Hierholzers_recursive(const string &current, vector<string> &final_path) {
        while (!g[current].empty()) {
            string rand_elm = *g[current].begin();
            g[current].erase(rand_elm);
            g[rand_elm].erase(current);
            _Hierholzers_recursive(rand_elm, final_path);
        }
        final_path.push_back(current);
    }

    // a graph has an eularian cycle iff every vertex has an even degree
    static bool isEularian(const Graph &g) {
        for (auto &adj : g.g) {
            if (adj.second.size() % 2 != 0)
                return false;
        }
        return true;
    }

};

void test()
{
    unordered_map<string, unordered_set<string>> graph =
    {
        { "0",{ "1","3" } },
        { "1",{ "2","0","4","5" } },
        { "2",{ "5","4","3","1" } },
        { "3",{ "2","0" } },
        { "4",{ "2","1" } },
        { "5",{ "1","2" } }
    };

    Graph g1(graph);
    EularianCycle ec1(g1);
    print(ec1.Hierholzers_iterative("0"));
    print(ec1.Hierholzers_recursive("0"));


    graph =
    {
        { "A",{ "B","D","C" } },
        { "B",{ "A","E","D","C" } },
        { "C",{ "B","A","D","E" } },
        { "D",{ "A","B","C" } },
        { "E",{ "B","C" } }
    };

    Graph g2(graph);
    EularianCycle ec2(g2);
    print(ec2.Hierholzers_iterative("A"));
    print(ec2.Hierholzers_recursive("A"));


    graph =
    {
        { "A",{ "B","F" } },
        { "B",{ "A","E","D","C" } },
        { "C",{ "B","E","D","F" } },
        { "D",{ "B","E","F","C" } },
        { "E",{ "F","B","D","C" } },
        { "F",{ "A","E","D","C" } }
    };

    Graph g3(graph);
    EularianCycle ec3(g3);
    print(ec3.Hierholzers_iterative("A"));
    print(ec3.Hierholzers_recursive("A"));


    vector<pair<string, string>> pair_graph =
        { { "JFK","SFO" },{ "JFK","ATL" },{ "SFO","ATL" },{ "ATL","JFK" },{ "ATL","SFO" } };

    Graph g4(pair_graph);
    EularianCycle ec4(g4);
    print(ec4.Hierholzers_iterative("JFK"));
    print(ec4.Hierholzers_recursive("JFK"));
}

int main() {
    test();
}

Testing

// Graph 1
0:      0
1:      1
2:      2
3:      5
4:      1
5:      4
6:      2
7:      3
8:      0



0:      0
1:      1
2:      2
3:      5
4:      1
5:      4
6:      2
7:      3
8:      0


// Graph 2
Graph does not contain eularian cycle


// Graph 3
0:      A
1:      B
2:      E
3:      F
4:      D
5:      B
6:      C
7:      E
8:      D
9:      C
10:     F
11:     A



0:      A
1:      B
2:      E
3:      F
4:      D
5:      B
6:      C
7:      E
8:      D
9:      C
10:     F
11:     A


// Graph 4 (not drawn)
0:      JFK
1:      SFO
2:      ATL
3:      JFK



0:      JFK
1:      SFO
2:      ATL
3:      JFK