Leetcode_207_Course Schedule

[lihe]

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?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0.
 So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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.

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

题意：已知有n个课程，标记从0到n-1，课程之间是有依赖关系的，已知n个课程的依赖关系，求是否可以将n个课程全部完成。

分析：将课程看做顶点，课程见的依赖关系看成有向边，构造有向图；如果图中无环，则可以完成全部课程，否则不能。

方法一：

算法思路：

1. 在深度优先搜索时，如果正在搜索某一顶点，又回到了该顶点，即证明图有环。

struct GraphNode{
    int label;
    std::vector<GraphNode*> neighbors;
    GraphNode(int x): label(x){}
};

bool DFS_graph(GraphNode* node, std::vector<int> &visit){
    visit[node -> label] = 0;
    for(int i = 0; i < node -> neighbors.size(); i++){
        if(visit[node -> neighbors[i] -> label] == -1){
            if(DFS_graph(node -> neighbors[i], visit) == 0){
                return false;
            }
        }
        else if(visit[node -> neighbors[i] -> label] == 0){
            return false;
        }
    }
    visit[node -> label] = 1;
    return true;
}

class Solution{
public:
    bool canFinish(int numCourse, std::vector<std::vector<int>> &prequisites){
        std::vector<GraphNode*> graph;
        std::vector<int> visit;
        for(int i = 0; i < numCourse; i++){
            graph.push_back(new GraphNode(i));
            visit.push_back(-1);
        }
        for(int i = 0; i < prequisites.size(); i++){
            GraphNode* begin = graph[prequisites[i][1]];
            GraphNode* end = graph[prequisites[i][0]];
            begin -> neighbors.push_back(end);
        }
        for(int i = 0; i < graph.size(); i++){
            if(visit[i] == -1 && !DFS_graph(graph[i], visit)){
                return false;
            }
        }
        for(int i = 0; i < numCourse; i++){
            delete graph[i];
        }
        return true;
    }
};

方法二：

算法思路：

1. 在宽度优先搜索是，只将入度为0的点添加至队列；
2. 当完成一个顶点的搜索后，它指向的所有顶点的入度都减一；
3. 若此时某顶点入度为0则添加至队列；
4. 完成搜索后，若所有的顶点入度都为0，则无环，否自有环。

struct GraphNode{
    int label;
    std::vector<GraphNode*> neighbors;
    GraphNode(int x): label(x){}
};

class Solution{
public:
    bool canFinish(int numCourse, std::vector<std::vector<int>> &prerequisites){
        std::vector<GraphNode*> graph;
        std::vector<int> degree;
        for(int i = 0; i < numCourse; i++){
            degree.push_back(0);
            graph.push_back(new GraphNode(i));
        }
        for(int i = 0; i < prerequisites.size(); i++){
            GraphNode* begin = graph[prerequisites[i][1]];
            GraphNode* end = graph[prerequisites[i][0]];
            begin -> neighbors.push_back(end);
            degree[prerequisites[i][0]]++;
        }
        std::queue<GraphNode*> Q;
        for(int i = 0; i < numCourse; i++){
            if(degree[i] == 0){
                Q.push(graph[i]);
            }
        }
        while(!Q.empty()){
            GraphNode* node = Q.front();
            Q.pop();
            for(int i = 0; i < node -> neighbors.size(); i++){
                degree[node -> neighbors[i] -> label]--;
                if(degree[node -> neighbors[i] -> label] == 0){
                    Q.push(node -> neighbors[i]);
                }
            }
        }
        for(int i = 0; i < graph.size(); i++){
            delete graph[i];
        }
        for(int i = 0; i < degree.size(); i++){
            if(degree[i]){
                return false;
            }
        }
        return true;
    }
};