Reconstruct Itinerary — Hierholzer's Eulerian Path

DFS from start node:
  While there are unvisited edges from u:
    Pick smallest lexical neighbor v
    Remove edge u→v
    DFS(v)
  Append u to result (post-order)
Result reversed = Eulerian path

from collections import defaultdict
import heapq

def findItinerary(tickets):
    adj = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(adj[src], dst)

    path = []

    def dfs(u):
        while adj[u]:
            v = heapq.heappop(adj[u])
            dfs(v)
        path.append(u)

    dfs("JFK")
    return path[::-1]

function findItinerary(tickets) {
    const adj={};
    for(const[s,d]of tickets){if(!adj[s])adj[s]=[];adj[s].push(d);}
    for(const k of Object.keys(adj))adj[k].sort().reverse();
    const path=[];
    const dfs=(u)=>{while(adj[u]&&adj[u].length)dfs(adj[u].pop());path.push(u);};
    dfs("JFK"); return path.reverse();
}

import java.util.*;
public List<String> findItinerary(List<List<String>> tickets) {
    Map<String,PriorityQueue<String>> adj=new HashMap<>();
    for(List<String>t:tickets)adj.computeIfAbsent(t.get(0),k->new PriorityQueue<>()).offer(t.get(1));
    LinkedList<String>path=new LinkedList<>();
    dfs("JFK",adj,path); return path;
}
void dfs(String u,Map<String,PriorityQueue<String>>adj,LinkedList<String>path){
    PriorityQueue<String>q=adj.get(u);
    while(q!=null&&!q.isEmpty())dfs(q.poll(),adj,path);
    path.addFirst(u);
}

#include <map>
#include <vector>
#include <string>
using namespace std;
map<string,multiset<string>> adj;
vector<string> path;
void dfs(string u){while(!adj[u].empty()){string v=*adj[u].begin();adj[u].erase(adj[u].begin());dfs(v);}path.push_back(u);}
vector<string> findItinerary(vector<vector<string>>&tickets){
    for(auto&t:tickets)adj[t[0]].insert(t[1]);
    dfs("JFK"); reverse(path.begin(),path.end()); return path;
}

/* C: adjacency list sorted alphabetically, DFS post-order, reverse result */