_1462.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

publicclass_1462 {
publicstaticclassSolution1 {
/*
 * My completely original solution.
 * DFS + part of topological sort (building the adjacency list)
 */
publicList<Boolean> checkIfPrerequisite(
intnumCourses, int[][] prerequisites, int[][] queries) {
List<Integer>[] graph = newArrayList[numCourses];
for (inti = 0; i < numCourses; i++) {
graph[i] = newArrayList<>();
 }
for (int[] pre : prerequisites) {
graph[pre[0]].add(pre[1]);
 }
List<Boolean> result = newArrayList<>();
// this cache is essential to speed things up, otherwise TLE on LeetCode
Map<String, Boolean> cache = newHashMap<>();
for (int[] query : queries) {
result.add(isPrereq(query[0], query[1], graph, cache));
 }
returnresult;
 }

privateBooleanisPrereq(
intpre, inttarget, List<Integer>[] graph, Map<String, Boolean> cache) {
if (pre == target) {
cache.put(pre + "-" + target, true);
returntrue;
 }
if (cache.containsKey(pre + "-" + target)) {
returncache.get(pre + "-" + target);
 }
for (intv : graph[pre]) {
if (isPrereq(v, target, graph, cache)) {
returntrue;
 }
 }
cache.put(pre + "-" + target, false);
returnfalse;
 }
 }

publicstaticclassSolution2 {
/*TODO: use BFS to solve this problem.*/
 }
}