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 4141x 4141x 414x 414x 414x 414x 414x 4141x 4141x 4141x 4141x 4141x 4141x 4141x 4141x 4141x 4141x 4141x 609x 609x 609x 609x 414x 303x 393x 2x 2x 609x 609x 609x 609x 4141x 4141x 609x 306x 306x 4141x 4141x 4141x 4141x | /**
* @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];
}
|