整体思路：
这是一道拓扑序列的题目，我们将边的方向定义成从先修课指向后修课的方向，借一下官方的题解图片，我们需要判断的是形成的这个图结构是否存在环，如果存在环，那么代表不能完成所有课程的学习。
bfs思路：
首先将每个点的入度数记录到hmap中，将每个点的后续节点记录到record中（record是一个unordered_map<int,vector<int>>结构，指的是某个节点指向的后续节点），首先遍历hmap中所有入度为0的节点，说明这些课程不需要先修课，他们可以直接被修完。将这些节点去掉，并且将该节点的后续节点的hmap值-1。再次遍历hmap，去掉入度数为0的节点....用什么结构来实现这个过程呢？队列~
代码：
C++：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//广度优先搜索---记录入度
unordered_map<int,int> hmap;
unordered_map<int,vector<int>> record; //记录该门课程的后续课程
int cnt=0;
//初始化hmap，record
for(int i=0;i<numCourses;i++){
hmap[i]=0;
}
int len=prerequisites.size();
for(int i=0;i<len;i++){
int a=prerequisites[i][0];
int b=prerequisites[i][1];
hmap[a]+=1;
record[b].push_back(a);
}
//将
deque<int> q;
//初始化q
unordered_map<int,int>::iterator iter=hmap.begin();
for(auto iter:hmap){
if(iter.second==0){
q.push_back(iter.first);
hmap[iter.first]=-1;
}
}
//
while(!q.empty()){
int p=q.front(); //该点入度为0，可删除
q.pop_front();
cnt++;
int len=record[p].size();
for(int i=0;i<len;i++){
hmap[record[p][i]]--;
}
for(auto iter:hmap){
if(iter.second==0){
q.push_back(iter.first);
hmap[iter.first]=-1;
}
}
}
if(cnt==numCourses){
return true;
}
else{
return false;
}
}
};注意这句代码：
unordered_map<int,int>::iterator iter=hmap.begin();Python：
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
hmap=[0]*numCourses
len_pre=len(prerequisites)
record=[[] for i in range(numCourses)]
cnt=0
for i in range(len_pre):
a=prerequisites[i][0]
b=prerequisites[i][1]
hmap[a]+=1
record[b].append(a)
q=deque()
for index,value in enumerate(hmap):
if value==0:
q.append(index)
hmap[index]=-1
while q:
p=q[0]
q.popleft()
cnt+=1
len_=len(record[p])
for i in range(len_):
hmap[record[p][i]]-=1
for index,value in enumerate(hmap):
if value==0:
q.append(index)
hmap[index]=-1
if cnt==numCourses:
return True
else:
return FalsePython中的deque需要 from collections import deque
注意这句代码：（替代vector<vector<int>>）
record=[[] for i in range(numCourses)] #正确
record=[[]]* numCourses #错误注意这句代码：（替代key为索引的字典/替代需要查找索引的list）
for index,value in enumerate(hmap):dfs思路：
我们利用hmap来记录节点 i 的邻接节点，利用flag来记录节点的状态（flag=0代表该点未被dfs，flag=1代表该点正在被路上的节点dfs，flag=-1代表该点已被其他节点dfs）。
大致dfs的思路是这样的（以节点 i 开始），首先判断节点 i 是否被其他节点 dfs（即flag=1），如果成立，则说明暂时无环，返回false。其次判断节点 i 是否属于正在被路上节点dfs，如果成立，则代表有环，返回true。如果该点未被访问，将该点的邻接节点依次遍历，遍历中如果有环，返回true，如果无环，将 i 节点的flag值记为-1。
代码：
C++：
class Solution {
public:
bool dfs(int i,unordered_map<int,vector<int>>& hmap,vector<int>& flag){
//以第i个点为起点
//有环返回true，无环返回false
if(flag[i]==1){return true;}
if(flag[i]==-1){return false;}
flag[i]=1;
int len=hmap[i].size();
for(int j=0;j<len;j++){
if(dfs(hmap[i][j],hmap,flag)){
return true;
}
}
flag[i]=-1;
return false;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int len=prerequisites.size();
unordered_map<int,vector<int>> hmap;
for(int i=0;i<len;i++){
hmap[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
vector<int> flag(numCourses,0);
for(int i=0;i<numCourses;i++){
if(dfs(i,hmap,flag)){
return false;
}
}
return true;
}
};Python：
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
def dfs(i,hmap:List[List[int]],flag:List[int]) -> bool:
if flag[i]==1:
return True
if flag[i]==-1:
return False
flag[i]=1
len_hmap=len(hmap[i])
for j in range(len_hmap):
if dfs(hmap[i][j],hmap,flag):
return True
flag[i]=-1
return False
len_pre=len(prerequisites)
hmap=[[]for _ in range(numCourses)]
for j in range(len_pre):
hmap[prerequisites[j][1]].append(prerequisites[j][0])
flag=[0]*numCourses
for j in range(numCourses):
if(dfs(j,hmap,flag)):
return False
return True
