Course Schedule

题目：

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?

分析：

题目本意就是寻找是否有cycle，其实就是做个topo sort看看是否存在的意思。

这道题目的dfs是一个典型的三色法判断是否有cycle

解法dfs：

class Solution {
public:
    bool dfs(int i, vector<vector<int> > &neighbors, vector<int> &visited) {
        visited[i] = 1;
        for (int j = 0; j < neighbors[i].size(); j++) {
            if (visited[neighbors[i][j] ] == 1) {
                return false;
            }
            if (visited[neighbors[i][j] ] == 0) {
                if (dfs(neighbors[i][j], neighbors, visited) == false) {
                    return false;
                }
            }
        }
        visited[i] = 2;
        return true;
    }

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int> > neighbors(numCourses, vector<int>() );
        for (int i = 0; i < prerequisites.size(); i++) {
            int first = prerequisites[i].first;
            int second = prerequisites[i].second;
            neighbors[second].push_back(first);
        }
        vector<int> visited(numCourses, 0);
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (dfs(i, neighbors, visited) == false) {
                    return false;
                }
            }
        }
        return true;
    }
};

解法bfs：

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int> > neighbors(numCourses, vector<int>() );
        for (int i = 0; i < prerequisites.size(); i++) {
            int first = prerequisites[i].first;
            int second = prerequisites[i].second;
            neighbors[first].push_back(second);
        }

        unordered_map<int, int> degree;
        for (int i = 0; i < neighbors.size(); i++) {
            for (int j = 0; j < neighbors[i].size(); j++) {
                if (degree.find(neighbors[i][j]) == degree.end() ) {
                    degree[neighbors[i][j]] = 1;
                } else {
                    degree[neighbors[i][j]] += 1;
                }
            }
        }

        queue<int> Q;
        for (int i = 0; i < numCourses; i++) {
            if (degree.find(i) == degree.end() ) {
                Q.push(i);
            }
        }

        int count = 0;
        while(!Q.empty() ) {
            int temp = Q.front();
            Q.pop();
            count++;
            for (int i = 0; i < neighbors[temp].size(); i++) {
                degree[neighbors[temp][i] ] -= 1;
                if (degree[neighbors[temp][i] ] == 0) {
                    Q.push(neighbors[temp][i]);
                }
            }
        }
        return (count == numCourses);
    }
};