Мосты и точки сочленения

1function findBridges(edges: Array<[a: string, b: string]>) {
2  const graph = buildAdj(edges)
3  const tin = new Map<string, number>()
4  const low = new Map<string, number>()
5  const bridges: Array<[string, string]> = []
6  let timer = 0
7 
8  function dfs(v: string, parent: string | null): void {
9    tin.set(v, low.set(v, ++timer).get(v)!)
10    for (const w of graph.get(v) ?? []) {
11      if (w === parent) continue
12      if (tin.has(w)) {
13        low.set(v, Math.min(low.get(v)!, tin.get(w)!)) // обратное ребро
14      } else {
15        dfs(w, v)
16        low.set(v, Math.min(low.get(v)!, low.get(w)!))
17        if (low.get(w)! > tin.get(v)!) {
18          bridges.push([v, w]) // мост: не вернуться выше v
19        }
20      }
21    }
22  }
23 
24  dfs(start, null)
25  return bridges
26}