There are n cities numbered from 1 to n and there are n-1 bidirectional roads such that all cities are connected. There are k temples, each one is in a different city. you are an athiest and currently in the 1st city. You want to visit city X such that neither X not the cities in the path from 1 to X has a temple. Find out how many such X you ca…

Athest_visits_city_nottemple_solution.js

process.stdin.resume();
process.stdin.setEncoding("utf-8");
var stdin_input = [];
process.stdin.on("data", function (input) {
    
    stdin_input.push(input.replace("\n", "").split(" ").map(Number));
});

process.stdin.on("end", function () {
   main(stdin_input);
});

function main(input) {
    let data = input;
    let [cities, temples] = input.shift();
    let templeArray = input.pop();
    let relation = {};
    let answer = [];
    for (let i = 1; i <= cities; i++) {
      relation[i] = new Set();
    }
    for (let i = 0; i < input.length; i++) {
      let [start, end] = input.shift();
      if (!templeArray.includes(end)) {
          relation[start].add(end);
      }
    }
    for (let i in relation) {
      relation[i] = Array.from(relation[i]);
    }


  function findRoute(currentCity, newcities, newPath) {
        while(relation[newCity].length) {
          newCity = relation[newCity].shift();
          newPath.push(newCity)
        }
        return newPath.length;
  }
    let total = [];

    for (let i in relation) {
      let newpath = [], newCity, x, y, z;
      for (let j = 0; j < relation[i].length; j++) {
        newpath = [];
        newCity = relation[i][j];
        newpath.push(newCity);
        
        if (newCity != cities && relation[newCity].length) {
          total.push(findRoute(newCity, relation[newCity].slice(0), newPath))
        } else {
          total.push(newpath.length);
        }
      }
    }
    answer = total.sort((a,b)=>b-a)[0];
    console.log(answer);   
}


// Sample input
//6 3 // 6 = total cities, 3 = total temples
//1 2 // route 1
//1 6 // route 2
//2 3 // route 3
//2 4 // route 4
//2 5 // route 5
//2 3 4 // temple present in cities 2, 3, 4

solution in nodejs.