K Path Query Codechef Solution | Codechef July Challenge 2021 | TechTalkBot


Code:- KPATHQRY
Name:- K Path Query
Codechef July 2021 long challenge

By TECHTALKBOT

You’re given a tree with  N N  vertices numbered from  1 1  to  N N . Your goal is to handle  Q Q  queries. For each query you are given  K K  nodes  v 1 , v 2 , … , v K v1,v2,…,vK . Find if there exists a simple path in the tree covering all the given vertices.


  1. /* package codechef; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Codechef {
  9.  public static void main (String[] args) throws java.lang.Exception {
  10.   // your code goes here
  11.   Scanner sc = new Scanner(System.in);
  12.  
  13.   int T = sc.nextInt();
  14.  
  15.   while(T-- > 0) {
  16.    int N = sc.nextInt();
  17.    Map<Integer, Set<Integer>> tree = new HashMap<>();
  18.    for(int i = 1; i < N; i++) addPath(tree, sc.nextInt(), sc.nextInt());
  19.  
  20.             int[] level = new int[N+1];
  21.             int[] parent = new int[N+1];
  22.    preProcess(tree, level, parent);
  23.  
  24.    int Q = sc.nextInt();
  25.    int[] visited = new int[N+1];
  26.    for(int i = 1; i <= Q; i++) {
  27.     int K = sc.nextInt();
  28.     int[] query = new int[K];
  29.     int maxDepth = 0;
  30.     int nodeWithMaxDepth = -1;
  31.     for(int j = 0; j < K; j++) {
  32.      query[j] = sc.nextInt();
  33.      if(level[query[j]] > maxDepth) {
  34.       maxDepth = level[query[j]];
  35.       nodeWithMaxDepth = query[j];
  36.      }
  37.     }
  38.  
  39.     boolean hasPath = process(nodeWithMaxDepth, parent, level, query, visited, i);
  40.     System.out.println(hasPath ? "YES" : "NO");
  41.    }
  42.   }
  43.  
  44.   sc.close();
  45.  }
  46.  
  47.  private static boolean process(int nodeWithMaxDepth, int[] parent, int[] level, int[] query, int[] visited, int marker) {
  48.   visitTillParent(nodeWithMaxDepth, parent, visited, marker);
  49.   int maxDepth = 0;
  50.   nodeWithMaxDepth = -1;
  51.   for(int q : query) {
  52.    if(visited[q] != marker && level[q] > maxDepth) {
  53.     maxDepth = level[q];
  54.     nodeWithMaxDepth = q;
  55.    }
  56.   }
  57.  
  58.   if(nodeWithMaxDepth == -1) return true;
  59.  
  60.   while(visited[nodeWithMaxDepth] != marker) {
  61.    visited[nodeWithMaxDepth] = marker;
  62.    nodeWithMaxDepth = parent[nodeWithMaxDepth];
  63.   }
  64.  
  65.   for(int q : query) {
  66.    if(visited[q] != marker || level[q] < level[nodeWithMaxDepth]) return false;
  67.   }
  68.   return true;
  69.  }
  70.  
  71.  private static void visitTillParent(int nodeWithMaxDepth, int[] parent, int[] visited, int marker) {
  72.   visited[nodeWithMaxDepth] = marker;
  73.   while(parent[nodeWithMaxDepth] != -1) {
  74.    nodeWithMaxDepth = parent[nodeWithMaxDepth];
  75.    visited[nodeWithMaxDepth] = marker;
  76.   }
  77.  }
  78.  
  79.  private static void preProcess(Map<Integer, Set<Integer>> tree, int[] level, int[] parent) {
  80.   boolean[] visited = new boolean[level.length];
  81.   Queue<Integer> bfsQueue = new LinkedList<>();
  82.  
  83.         int u = 1;
  84.   parent[u] = -1;
  85.   level[u] = 0;
  86.   bfsQueue.add(u);
  87.   visited[u] = true;
  88.  
  89.   while(!bfsQueue.isEmpty()) {
  90.    int n = bfsQueue.size();
  91.    while(n-- > 0) {
  92.     int parentNode = bfsQueue.poll();
  93.     Set<Integer> children = tree.get(parentNode);
  94.     for(Integer child : children) {
  95.      if(!visited[child]) {
  96.       parent[child] = parentNode;
  97.       level[child] = level[parentNode]+1;
  98.       visited[child] = true;
  99.       bfsQueue.add(child);
  100.      }
  101.     }
  102.    }
  103.   }
  104.  }
  105.  
  106.  private static void addPath(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
  107.   addEdge(tree, u, v);
  108.   addEdge(tree, v, u);
  109.  }
  110.  
  111.  private static void addEdge(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
  112.   if(!tree.containsKey(u)) tree.put(u, new HashSet<>());
  113.   tree.get(u).add(v);
  114.  }
  115. }