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 4008x 4008x 398x 398x 398x 398x 398x 4008x 4008x 4008x 4008x 4008x 4008x 4008x 4008x 4008x 4008x 4008x 588x 588x 588x 588x 398x 303x 397x 2x 2x 588x 588x 588x 588x 4008x 4008x 588x 285x 285x 4008x 4008x 4008x 4008x | /**
* @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];
}
|