n cities from 1 to n
n - 1 bidirectional roads s.t all cities are connected.
k temples - each in a different city.
starting from 1, want to visit a city x s.t neither x nor cities in the path from 1 to x has a temple.
How many x can be visted?
Test Cases:
{
edges: [
[1, 2],
[1, 6],
[2, 3],
[2, 4],
[2, 5],
],
templesArray: [2, 3, 4],
}Solution
class Graph {
constructor() {
this.adjacencyList = {}
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []
}
addEdge(vertex1, vertex2) {
this.addVertex(vertex1)
this.addVertex(vertex2)
this.adjacencyList[vertex1].push(vertex2)
this.adjacencyList[vertex2].push(vertex1)
}
findUnholy(skip) {
const stack = [1]
skip.set(1, true)
let result = 0
while (stack.length) {
const currentVertex = stack.pop()
skip.set(currentVertex, true)
this.adjacencyList[currentVertex].forEach((neighbor) => {
if (!skip.get(neighbor)) {
stack.push(neighbor)
result++
}
})
}
return result
}
}
function unholyPaths({edges, templesArray}) {
const graph = new Graph()
for (const edge of edges) {
const [v1, v2] = edge
graph.addEdge(v1, v2)
}
const temples = new Map()
for (const temple of templesArray) {
const key = parseInt(temple)
temples.set(key, true)
}
const xNumber = graph.findUnholy(temples)
return xNumber
}