Эйлеров путь (алгоритм Хирхольцера)

O(E)

Соединяем рёбра так, чтобы прибытие по одному было отправлением по следующему, используя каждое ребро ровно один раз. Обычный жадный обход может оставить неиспользованные рёбра в тупике, поэтому алгоритм Хирхольцера идёт вперёд до упора, записывает тупик и возвращается назад, чтобы закрыть остальное.

Сигналы

использовать каждое ребро ровно один развосстановить маршрут по билетамрисунок одним росчерком / не отрывая ручкупройти каждую дорогу/домино ровно один разрейсы или домино должны соединиться в одну поездку

Шаблон

function eulerianPath(tickets, start) {
    const adj = {};
    for (const [from, to] of tickets) {
        (adj[from] ||= []).push(to);
    }
    for (const from in adj) adj[from].sort().reverse(); // pop smallest first
    const route = [];
    const stack = [start];
    while (stack.length) {
        const node = stack[stack.length - 1];
        if (adj[node] && adj[node].length) {
            stack.push(adj[node].pop());
        } else {
            route.push(stack.pop()); // dead end: record and back up
        }
    }
    return route.reverse();
}

Похоже, но не то

Обход графа BFS / DFS: Эйлеров путь должен использовать каждое РЕБРО ровно один раз (алгоритм Хирхольцера), а BFS/DFS посещает каждый УЗЕЛ один раз и не заботится о том, сколько раз использовано ребро.

E до ~1e5 билетов/рёбер, нужно использовать каждое ребро ровно один раз -> O(E): постпорядковый откат Хирхольцера посещает каждое ребро один раз.

Изучить этот паттерн