Instantly share code, notes, and snippets.

# lyleaf/210. Course Schedule II.cpp

Last active August 19, 2016 05:23
Show Gist options
• Save lyleaf/75a05af347687d3b8b56ca115d631ae0 to your computer and use it in GitHub Desktop.
Topological Sort Using BFS/DFS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 我的naive方法如下。大体上是正确的BFS，就是每一次找出没有入的节点，放到答案的vector里面去。 如何找出没有入的节点呢？我用的是每一次都用一个新的数组prerequisites来看。每一次就把prerequisites中已经放入vector的course的约束删除。但这 样每一回都要新建一个prerequisites vector. 为什么不直接用一个degree来标志入节点的个数呢？ */ class Solution { public: vector findOrder(int numCourses, vector>& prerequisites) { vector result; while (result.size() != numCourses){ vector course(numCourses); vector> pre; for (auto i: result){ course[i] = 1; } bool flag = false; for (auto i: prerequisites) course[i.first]=1; set s; for (int i=0;i r; return r; } pre.swap(prerequisites); } return result; } };
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 我的方法中，一个循环里面有两个循环，而且每次找一个节点的入节点的时候，总是要遍历所有的prerequisites数组。我们可以想到用一个邻节点图来 表示我们的图。然后使用一个临时的queue来存放每一轮被删除的节点。 */ class Solution { public: vector findOrder(int numCourses, vector>& prerequisites) { vector result; vector inDegree(numCourses);//inDegree[n] means how many courses should have learned before a course n+1 for (auto p: prerequisites){ inDegree[p.first] ++; } while (result.size() != numCourses){ bool flag = false; vector deleted; for (int i=0;i r; return r; } } return result; } };