美文网首页
刷题(15)Topological Sort

刷题(15)Topological Sort

作者: MuMuMiu | 来源:发表于2022-01-29 04:06 被阅读0次

    leetcode 207. Course Schedule , 210. Course Schedule ii

    基本上都是可以用backtracking做的,思路也很简单。但是碰到这些graph traversal 的一般来说用Topological Sort比较简单,就是看每个vertex有没有indegree的edge。

    time complexity和space complexity 一般都是O(V+E)  点和边

    310. Minimum Height Trees

    这道题目比较tricky的地方是,如果一个比较直观的solution,用Topological sort做,那么它有一个结论是,通过剪枝最后剩下的那一个或者两个就是最小高度树的树根。

    相关文章

      网友评论

          本文标题:刷题(15)Topological Sort

          本文链接:https://www.haomeiwen.com/subject/euyxkrtx.html