没有输出的输入是不完整的

0%

leetcode-207-CourseSchedule

发表于 分类于
本文字数： 2.7k 阅读时长 ≈ 3 分钟

这个是leetcode中为数不多的关于Graph的题目，判断图中是否有环，可以用BFS或者DFS两种思路进行求解。

题目描述

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

Example 1

1
2
3
4
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

1
2
3
4
5
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.

解题思路

BFS或者DFS

详细解释

其实这个题目就是说对于每一个课程都有一个前置课程，然后问如果前置课程这样安排能不能成立，其实就可以抽象出查看一个图中是否有环，因为一旦有环路，那肯定是不成立的，反之，肯定成立。

BFS思路

我们创建一个队列，用于保存目前入度为0的点，然后我们对于每个节点都保存一个入度的值。然后从入度为0的值开始，进行遍历，对于这个点能达到的所有的点将其入度减去1，如果此时这个点入度为0，将其加入到队列中。当队列为空的时候，如果此时所有节点的入读都变成0，那么肯定没有环路，否则有环路。
举例说明,假设输入是如下情况

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

对应的图其实就是

1.初始化队列q中元素只有0，入度数组arr=[0,2,1,1]
2. 然后经过0号节点，arr变为[0,1,0,1],此时2号加入队列
3. 然后处理2号节点，arr变成[0,0,0,1],此时1号加入队列
4. 然后处理1号节点，arr变成[0,0,0,0] 此时3号加入队列
5. 然后处理3号节点，arr变成[0,0,0,0] 此时队列为空。
6. 然后判断arr数组中每个节点的入度是否是0，全为0，返回true。

DFS思路

DFS就是用深度优先搜索，我们对于每个节点记录一个状态，-1表示是当前节点：如果在遍历过程中发现了-1，说明又回到了自身，那就是有环路，返回flase；0是默认值，代表之前还没有访问；1表示已经访问过了。对于每一个节点都进行如此的遍历，即可得到结果。
PS：要记得传引用而不要传对象本身，否则容易Time Limit Exceeded

解题代码

BFS解题代码

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses,vector<int>());
        vector<int> in(numCourses,0);
        for(auto a:prerequisites){
            graph[a[1]].push_back(a[0]);
            in[a[0]]++;
        }
        
        queue<int> q;
        for(int i = 0;i<in.size();i++){
            if(in[i]==0) q.push(i);
        }
        
        while(!q.empty()){
            auto a = q.front(); q.pop();
            for(int b:graph[a]){
                --in[b];
                if(in[b]==0) q.push(b);
            }
        }
        
        for(int i:in){
            if(i!=0) return false;
        }
        return true;
    }
};

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses,vector<int>());
        vector<int> visit(numCourses);
        for(auto a:prerequisites){
            graph[a[1]].push_back(a[0]);
        }
        for(int i = 0; i < numCourses; ++i){
            if(!findSelf(graph,visit,i)) return false;
        }
        return true;
    }
    bool findSelf(vector<vector<int>>& graph,vector<int>& visit,int i){
        if(visit[i] == -1) return false;
        if(visit[i] == 1) return true;
        visit[i] = -1;
        for(auto a:graph[i]){
            if(!findSelf(graph,visit,a)) return false;
        }
        visit[i] = 1;
        return true;
    }
};

以上，本题结束！