Setu | OA | Unholy Paths (Graph)
340

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
}
Comments (1)