Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for [old] What Is Wrong With This Family? by Moff
function isFamily(tree) {
let graph = {};
let parents = {};
let vertices = new Set();
tree.forEach(([v1, v2]) => {
parents[v1] = parents[v1] || 0;
parents[v2] = parents[v2] || 0;
vertices.add(v1);
vertices.add(v2);
if (v1 === v2)
return false; // self loop
graph[v1] = graph[v1] || [];
graph[v2] = graph[v2] || [];
graph[v1].push(v2);
parents[v2] += 1;
});
let grandfather = [];
for (let k in parents) {
if (parents[k] === 0)
grandfather.push(k);
}
if (vertices.size - tree.length !== 1)
return false; // tree checker
if (grandfather.length !== 1)
return false; // only one grandfather
// BFS
let x = grandfather[0];
let queue = [x];
let visited = [x];
while (queue.length) {
x = queue.pop();
for (let v of graph[x]) {
if (!visited.includes(v)) {
visited.push(v);
queue.unshift(v);
}
}
}
return visited.length === vertices.size;
}
July 31, 2017
