你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
示例 2:
输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。
解法:拓扑排序判断有向图是否有环
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> edge[numCourses];//邻接表
vector<int> indegree(numCourses,0);//入度
vector<int> ans;
queue<int> q;//如果要按字典序排序则要换成优先队列
for(int i = 0;i<prerequisites.size();i++){
//例[[1,0]] 0指向1
edge[prerequisites[i][1]].push_back(prerequisites[i][0]);
indegree[prerequisites[i][0]]++;
}
for(int i = 0;i<numCourses;i++){
if(!indegree[i]) q.push(i);
}
while(!q.empty()){
int temp = q.front();
q.pop();
ans.push_back(temp);
//遍历所有以temp为入度节点
for(int i = 0;i<edge[temp].size();i++){
int y = edge[temp][i];
indegree[y]--;//入度减一
if(indegree[y]==0) q.push(y);
}
}
return ans.size() == numCourses;
}
};
错误解法: 并查集只能判断无向图
//并查集只能判断无向图
class Solution {
public:
vector<int> father;
int find(int x){
if(x==father[x]) return x;
else
father[x] = find(father[x]);
return father[x];
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
for(int i = 0;i<numCourses;i++)
father.push_back(i);
for(int i = 0;i<prerequisites.size();i++){
int father_a = father[prerequisites[i][0]];
int father_b = father[prerequisites[i][1]];
if(father_a==father_b) return false;
father[father_a] =father_b;
}
return true;
}
};