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 4063x 4063x 395x 395x 395x 395x 395x 4063x 4063x 4063x 4063x 4063x 4063x 4063x 4063x 4063x 4063x 4063x 586x 586x 586x 586x 395x 298x 392x 2x 2x 586x 586x 586x 586x 4063x 4063x 586x 288x 288x 4063x 4063x 4063x 4063x | /**
* @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];
}
|