207. Course Schedule

problem description

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:

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

algorithm thought

学习一门课程之前要学习先学课程，如果有两门课程是互相满足的，那就学不完。如果把这种关系构成一个图，第一个能学的课程一定是入度为0的。然后将第一个课程在图中删除，第二个能学的肯定也是入度为0的。这种处理就是拓扑排序。可以利用拓扑排序解决这题

code

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses);
        for(int i=0;i<prerequisites.size();++i){
            graph[prerequisites[i].first].push_back(prerequisites[i].second);
            indegree[prerequisites[i].second]++;
        }
        while(numCourses){
            int tmp=-1;
            for(int i=0;i<indegree.size();++i){
                if(indegree[i]==0){
                    tmp=i;
                    indegree[i]=INT_MAX;
                    numCourses--;
                    break;
                }
            }
            if(tmp==-1)
                return false;
            for(int i=0;i<graph[tmp].size();++i){
                indegree[graph[tmp][i]]--;
            }
        }
        return true;
    }
};

algorithm analysis

建图的过程时间复杂度和空间复杂度都是O(n²)，找到一个入度为0的节点，平均时间复杂度为O(n)。删除一个节点，时间复杂度O(n)。第二个循环平均进行n次，循环总的时间复杂度为O(n²)。最后时间复杂度O(n²)