graphs-general
1234567891011121314151617181920212223242526272829303132333435363738394041424344
const graph = [
[1],
[0, 2, 4, 5],
[1, 4, 5],
[],
[5, 2, 1],
[1, 2, 4],
];
function validateAdjacencyList(graph) {
const nodesCount = graph.length;
for (let node = 0; node < nodesCount; node++) {
const seen = new Set();
for (const nbr of graph[node]) {
// Every node is between 0 and V - 1.
if (nbr < 0 || nbr >= nodesCount) return false;
// There are no self-loops.
if (node === nbr) return false;
// There are no parallel edges.
if (seen.has(nbr)) return false;
seen.add(nbr);
}
}
// If node1 appears in graph[node2], then node2 also appears in graph[node1].
const edges = new Set();
for (let node1 = 0; node1 < nodesCount; node1++) {
for (const node2 of graph[node1]) {
const edge = `[${Math.min(node1, node2)}, ${Math.max(node1, node2)}]`;
if (edges.has(edge)) edges.delete(edge);
else edges.add(edge);
}
}
return edges.size === 0;
}
const verdict = validateAdjacencyList(graph);
console.log(verdict);
JavaScript
INFO