Эйлеров путь

1function eulerianPath(edges: Array<[a: string, b: string]>) {
2  const deg = new Map<string, number>()
3  for (const [a, b] of edges) {
4    deg.set(a, (deg.get(a) ?? 0) + 1)
5    deg.set(b, (deg.get(b) ?? 0) + 1)
6  }
7  const odd = [...deg.keys()].filter((v) => deg.get(v)! % 2 === 1)
8  // Эйлер: 0 или 2 нечётных; путь начинается в одной нечётной
9 
10  const graph = buildAdj(edges)
11  const stack = [odd[0] ?? start]
12  const path: string[] = []
13 
14  while (stack.length > 0) {
15    const v = stack[stack.length - 1]!
16    if ((graph.get(v) ?? []).length > 0) {
17      const w = graph.get(v)!.pop()!
18      graph.get(w)!.splice(graph.get(w)!.indexOf(v), 1)
19      stack.push(w) // идём по ребру, удаляя его
20    } else {
21      path.push(stack.pop()!) // тупик — в ответ
22    }
23  }
24 
25  return path.reverse()
26}