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 3959x 3959x 399x 399x 399x 399x 399x 3959x 3959x 3959x 3959x 3959x 3959x 3959x 3959x 3959x 3959x 3959x 589x 589x 589x 589x 399x 303x 394x 2x 2x 589x 589x 589x 589x 3959x 3959x 589x 286x 286x 3959x 3959x 3959x 3959x | /**
* @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];
}
|