Leetcode 207/Leetcode 210: course schedule I II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

The input prerequisites is a graph represented by a list of edges, not adjacency matrices.

这个题目很容易分析出来是check if a directed graph has a cycle.

但是给的graph是 a list of edges， 如果只给定一些edges我们是无法对graph进行遍历的，所以我们可以建立一个adjacent list, 并且带上一个state记录每个node的状态。

这个题目里面的adjacent list 可以用map来做， 然后对map做DFS遍历。
采用的是DFS + mark visitIII -> 3 states
但是需要注意的是，需要对graph里面的每个Node进行遍历，才能遍历到所有的可能。
 这个题目里面没有 sanity check ！！！ 面试的时候要跟面试官商量sanity check的问题。 
class Solution {
private:
    bool dfs(map<int, vector<int>> &nmap, int start, vector<int> &M) {
        //base case
        if (M[start] == 1) return true;//has visited
        if (M[start] == -1) {
            return false;
        }
        M[start] = -1; //visiting node
        //expand
        for (int i = 0; i < nmap[start].size();i++) {
           if(dfs(nmap, nmap[start][i], M) == false) return false;
        }
        M[start] = 1; //mark visit
        return true;
    }
public:
    //to check if a directed graph has a cycle or not
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //map
        map<int, vector<int>> nmap;
        for (int i = 0; i < prerequisites.size(); i++) {
            nmap[prerequisites[i].second].push_back(prerequisites[i].first);//prere->course
        }
        //use map to do dfs + visit
        vector<int> M(numCourses, 0); //unvisited
        for (int i = 0; i < numCourses;i++) {
            if (dfs(nmap, i, M) == false) return false;
        }
        return true;
    }
};
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

这个题目读完就是一个明显的topological sort的问题。
 topological sort DFS写法的一般思路： DFS+ mark visit III, 每次当一个点被mark成visited，之后将这个点加入rst中。
注意在用DFS + mark visit III之前，graph的表示是 course ->  pre-dependency,与判断directed graph里面有没有circle是相反的表示方式。

L ← Empty list that will contain the sorted nodes

for each of the node n in the graph do

visit(n)

function visit(node n)

if n is visited then return   

if n is visiting then stop (not a DAG, there is a cycle)

if n is not visited or visiting then

mark n visiting

                        for each node m which is n’s dependency do            

visit(m)        

      mark n visited        

      add n to head of L

class Solution {
private:
    bool visit(int start, unordered_map<int, vector<int>> &gmap, int *M, vector<int> &rst) {
        //base case
        if (M[start] == 1) return true;
        if (M[start] == -1) return false; //cycle
        //mark
        M[start] = -1;//mark visiting
        for (int i = 0; i < gmap[start].size();i++) {
            if (visit(gmap[start][i], gmap, M, rst) == false) return false;
        }
        M[start] = 1; //visited
        rst.push_back(start);
        return true;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> rst;
        unordered_map<int, vector<int>> gmap;
        for (int i = 0; i < prerequisites.size(); i++) {
            gmap[prerequisites[i].first].push_back(prerequisites[i].second);
        }
        //vector<int> M(numCourses, 0);
        int M[numCourses] = {0};
        //for each node in the graph do visit n
        for (int i = 0; i < numCourses; i++) {
            if (visit(i, gmap, M, rst) == false) {
                rst.clear();
                break;
            }
        }
        return rst;
    }
};