欧拉回路与一笔画

// 无向图，邻接表 + 边删除
Map<Integer, Queue<Integer>> adj = new HashMap<>();
List<Integer> circuit = new ArrayList<>();

void hierholzer(int u) {
    Queue<Integer> neighbors = adj.getOrDefault(u, new LinkedList<>());
    while (!neighbors.isEmpty()) {
        int v = neighbors.poll();
        adj.get(v).remove(Integer.valueOf(u)); // 删除反向边
        hierholzer(v);
    }
    circuit.add(u); // 后序加入
}

// 使用
hierholzer(start);
Collections.reverse(circuit); // 反转得到欧拉回路

Map<Integer, Queue<Integer>> adj = new HashMap<>();
List<Integer> path = new ArrayList<>();

void dfs(int u) {
    Queue<Integer> q = adj.getOrDefault(u, new LinkedList<>());
    while (!q.isEmpty()) {
        int v = q.poll();
        dfs(v);
    }
    path.add(u);
}

// 有向图欧拉路径
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<>()).add(t.get(1));
    }
    List<String> result = new ArrayList<>();
    dfs("JFK", adj, result);
    Collections.reverse(result);
    return result;
}

void dfs(String u, Map<String, PriorityQueue<String>> adj, List<String> result) {
    PriorityQueue<String> pq = adj.getOrDefault(u, new PriorityQueue<>());
    while (!pq.isEmpty()) {
        dfs(pq.poll(), adj, result);
    }
    result.add(u);
}