Topological Sort Using BFS/DFS

210. Course Schedule II.cpp

/*
我的naive方法如下。大体上是正确的BFS，就是每一次找出没有入的节点，放到答案的vector里面去。
如何找出没有入的节点呢？我用的是每一次都用一个新的数组prerequisites来看。每一次就把prerequisites中已经放入vector的course的约束删除。但这
样每一回都要新建一个prerequisites vector.
为什么不直接用一个degree来标志入节点的个数呢？
*/


class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> result;
        while (result.size() != numCourses){
            vector<int> course(numCourses);
            vector<pair<int, int>> pre;
            for (auto i: result){
                course[i] = 1;
            }
            bool flag = false;
            for (auto i: prerequisites) course[i.first]=1;
            set<int> s;
            for (int i=0;i<numCourses;i++){
                if (course[i]==0) {
                    flag = true;
                    s.insert(i);
                    result.push_back(i);
                }
            }
            
            for (auto j: prerequisites){
                if (s.find(j.second)==s.end())
                    pre.push_back(j);
            }


            if (!flag && result.size()!=numCourses) {
                vector<int> r;
                return r;
            }
            pre.swap(prerequisites);

        }
        return result;
    }
};

My Way Of Using inDegree.cpp

/*
我的方法中，一个循环里面有两个循环，而且每次找一个节点的入节点的时候，总是要遍历所有的prerequisites数组。我们可以想到用一个邻节点图来
表示我们的图。然后使用一个临时的queue来存放每一轮被删除的节点。
*/

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> result;
        
        vector<int> 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<int> deleted;
            
            for (int i=0;i<numCourses;i++){
                if (inDegree[i] == 0){
                    flag = true;
                    result.push_back(i);
                    deleted.push_back(i);
                }
            }
            
            for (auto d: deleted){
                inDegree[d]--;
                for (auto p: prerequisites){
                    if (p.second == d)
                    inDegree[p.first] --;
                }
            }
            
            if (!flag && result.size()!=numCourses) {
                vector<int> r;
                return r;
            }

        }
        return result;
    }
};

未完待续。