题目:
思想:
一开始的想法是构建有向图,然后在有向图中找到query的两个点是否有父子关系。
但看了ylb的答案后,发现先计算出可达性更快。
首先遍历prerequirements,将所有的可达性记录下来。
然后三重循环,连接所有的可达性。
i->j->k,如果i->k,那么i->k就是可达的。
代码:
1 | class Solution: |
一开始的想法是构建有向图,然后在有向图中找到query的两个点是否有父子关系。
但看了ylb的答案后,发现先计算出可达性更快。
首先遍历prerequirements,将所有的可达性记录下来。
然后三重循环,连接所有的可达性。
i->j->k,如果i->k,那么i->k就是可达的。
1 | class Solution: |