题目

题目意思是某个课需要另外一个课作为先修课，需要判断所有课程能不能完成，不能完成的情况是这些课程形成了环。
例如：

1
2
Input: 3, [[1,2],[0,1],[2,0]]
2->1->0->2 形成了环，这样就不能完成课程，返回false

方法一 dfs

可以直接暴力对所有节点DFS，然后在每个节点DFS时判断之前是否以及访问当前节点，如果已经访问则返回false，否则继续向下DFS。这样时间复杂度是O(n^2),因此使用finished记录已经访问过的节点是否能完成的信息，再之后再次访问时不需要继续DFS，使得时间复杂度下降。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {        
        vector<vector<int> > edges(numCourses, vector<int>(numCourses, -1));
        for (pair<int, int> pair : prerequisites) {
            edges[pair.second][pair.first] = 1;
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, edges)) return false;
        }
        return true;      
    }
    bool dfs(int start, vector<vector<int> > & edges) {
        if (finished.find(start) != finished.end()) return true;
        for (int i = 0; i < edges[start].size(); i++) {
            if (edges[start][i] == -1) continue;
            if (visited.find(i) != visited.end()) return false;
            visited.insert(i);
            if(!dfs(i, edges)) return false;
            finished.insert(i);
            visited.erase(i);
        }
        return true;
    }
    unordered_set<int> visited;
    unordered_set<int> finished;
};

时间复杂度O(n)

方法二 BFS

因为拓扑排序是不能包括环的，所以直接判断能否拓扑排序，就能知道是否能完成。
使用BFS来实现拓扑排序，需要队列以及获得节点的入度，首先入度为0的节点被访问，然后将相关联的节点度减一，直到入度为0，再次入队，最后判断能否将所有节点访问，如果不能就false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
        vector<vector<int> > edges(numCourses, vector<int>(numCourses, -1));
        for (pair<int, int> pair : prerequisites) {
            edges[pair.second][pair.first] = 1;
            indegree[pair.first]++;
        }
        queue<int> starts;
        
        for (int i = 0; i < indegree.size(); i++) {
            if (indegree[i] == 0) {
                starts.push(i);
            }
        }
        while (!starts.empty()) {
            numCourses--;
            int start = starts.front();
            starts.pop();
            for (int end = 0; end < edges[start].size(); end++) {
                if (edges[start][end] == -1) continue;
                indegree[end]--;
                if (indegree[end] == 0) {
                    starts.push(end);
                }
            }
        }
        return numCourses == 0;     
    }
};

时间复杂度O(n)