1462. Course Schedule IV

Solution idea

Topological Sort

思路总结

1. 思路的两次转折: 一开始的想法是用BFS找每一个query的路径，但会out of memory。
   • :arrow_right: 经提示，可以用 Topological Sort，用一个 "继承"变量，剥洋葱的时候沿途记录 course i 是哪些课的 prerequisites。所以，想的是定义 []map[int]bool: key = prerequisite, value = courses. 但是，发现这样定义的变量在"剥洋葱"的时候并不容易更新。
   • :arrow_right: 后经提示，反过来想，定义 []map[int]bool: key = course i, value = all prerequisites of course i (DP的思路)，这样就容易多了，每次往下一层剥的时候，当前节点cur的所有prerequisites就可以都知道并加进下一个节点中。
2. Base Case: course i is prerequisite of itself. 这样, 在更新下一个节点的prerequisites的时候就可以把cur也加进去，而不会只加进去cur的prerequisites而造成遗漏

Resource

【每日一题】1462. Course Schedule IV, 7/23/2020