Press n or j to go to the next uncovered block, b, p or k for the previous block.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | 2x 2x 2x 2x 2x 2x 3819x 3819x 341x 341x 341x 341x 341x 3819x 3819x 3819x 3819x 3819x 3819x 3819x 3819x 3819x 3819x 3819x 505x 505x 505x 505x 341x 276x 337x 1x 1x 505x 505x 505x 505x 3819x 3819x 505x 229x 229x 3819x 3819x 3819x 3819x | /** * @template T * @param {Array<[T, T]>} edges * @returns {Array<T>|undefined} */ export default function check_graph_for_cycles(edges) { /** @type {Map<T, T[]>} */ const graph = edges.reduce((g, edge) => { const [u, v] = edge; if (!g.has(u)) g.set(u, []); if (!g.has(v)) g.set(v, []); g.get(u).push(v); return g; }, new Map()); const visited = new Set(); const on_stack = new Set(); /** @type {Array<Array<T>>} */ const cycles = []; /** * @param {T} v */ function visit(v) { visited.add(v); on_stack.add(v); graph.get(v)?.forEach((w) => { if (!visited.has(w)) { visit(w); } else if (on_stack.has(w)) { cycles.push([...on_stack, w]); } }); on_stack.delete(v); } graph.forEach((_, v) => { if (!visited.has(v)) { visit(v); } }); return cycles[0]; } |