Flight Itinerary Sequel - Amazon Top Interview Questions

                        Solution in C++ :

vector<string> solve(vector<vector<string>>& flights) {
    map<string, set<string>> graph;
    map<string, int> ind;
    for (auto& v : flights) {
        graph[v[0]].insert(v[1]);
        ind[v[1]]++;
        ind[v[0]];
    }

    set<pair<string, string>> used_edge;
    vector<string> ans;

    function<bool(const string&)> dfs = [&](const string& node) -> bool {
        ans.push_back(node);
        if (used_edge.size() == flights.size()) return true;
        for (auto& s : graph[node]) {
            if (used_edge.count({node, s})) continue;
            used_edge.insert({node, s});
            if (dfs(s)) return true;
            used_edge.erase({node, s});
        }
        ans.pop_back();
        return false;
    };

    bool check = false;
    for (auto& p : ind) {
        if (p.second == 0) {
            dfs(p.first);
            check = true;
            break;
        }
    }
    if (!check) {
        for (auto it = graph.begin(); it != graph.end(); it++)
            if (dfs(it->first)) break;
    }

    return ans;
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, flights):
        graph = defaultdict(list)
        degree = defaultdict(int)  # + in  - out

        for u, v in flights:
            graph[u].append(v)
            degree[u] -= 1
            degree[v] += 1

        for outgoing in graph.values():
            outgoing.sort(reverse=True)

        res = []
        path_start = min(degree, key=degree.__getitem__)
        circuit_start = min(graph)

        def dfs(u, graph):  # Hierholzer
            while graph[u]:
                v = graph[u].pop()
                dfs(v, graph)

            res.append(u)

        if degree[path_start] == -1:  # eulerian path ?
            dfs(path_start, graph)
        else:  # eulerian circuit
            dfs(circuit_start, graph)

        return res[::-1]