相关题目： 210 课程表2
1.官方题解：
这是一题经典的「拓扑排序」问题
给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：对于图 G 中的任意一条有向边 (u,v)，u 在排列中都出现在 v 的前面那么称该排列是图 G 的「拓扑排序」
*1.如果图 G 中存在环(即图 G 不是「有向无环图」)，那么图 G 不存在拓扑排序。这是因为假设图中存在环 “x1,x2，…,„,í，那么 x1在排列中必须出现在 xn 的前面，但 xn同时也必须出现在 x1的前面，因此不存在一个满足要求的排列，也就不存在拓扑排序
*2.如果图 G 是有向无环图，那么它的拓扑排序可能不止一种。举一个最极端的例子，如果图 G 值包含n个节点却没有任何边，那么任意一种编号的排列都可以作为拓扑排序
有了上述的简单分析，我们就可以将本题建模成一个求拓扑排序的问题了
我们将每一门课看成一个节点
如果想要学习课程 A 之前必须完成课程 B，那么我们从 B 到 A 连接一条有向边。这样以来，在拓扑排序中，B一定出现在 A 的前面。
1.1深搜
从出度思考(从后往前排序)， 出度为0的节点在拓扑排序中一定排在后面, 然后删除和该节点对应的边, 迭代寻找出度为0的节点
我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈来存储所有已经搜索完成的节点。
对于一个节点 u，如果它的所有相邻节点都已经搜索完成，那么在搜索回溯到u的时候，u本身也会变成一个已经搜索完成的节点。这里的「相邻节点」指的是从u出发通过一条有向边可以到达的所有节点。
假设我们当前搜索到了节点u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把u入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 u 处于栈顶的位置，那么 u 出现在所有 u 的相邻节点的前面。因此对于 u 这个节点而言，它是满足拓扑排序的要求的。
这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。
c++版本
//一个二维向量，用于表示课程之间的依赖关系，每个元素`edges[u]`表示依赖先修课程`u`的课程。
//`visited`：用于标记课程的访问状态，0表示未访问，1表示正在访问，2表示已访问。
//`valid`：表示当前的课程安排是否有效，初始值为`true`
class Solution{
private:
vector<vector<int>> edges;
vector<int> visited;
bool valid = true;
public:
//用于从课程`u`开始进行深度优先遍历。在遍历过程中，会对课程进行标记，同时检查是否存在环路。若存在环路，则将`valid`设为`false`，表示无法完成所有课程。
void dfs(int u)
{
visited[u] = 1;//从课程`u`开始进行深度优先遍历
for(int v:edges[u])//遍历课程u的先修课程
{
if(visited[v] == 0)//如果有没访问的先修课程
{
dfs(v);//dfs
if(!valid)
{
return;
}
}
else if(visited[v] ==1)//出现环路
{
valid = false;//直接置为false
return;
}
}
visited[u] =2;//u这个课程 已访问结束
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)//函数实现
{
//根据输入的先修课程信息，构建课程之间的依赖关系
edges.resize(numCourses);
visited.resize(numCourses);
for (const auto& info:prerequisites)
{
edges[info[1]].push_back(info[0]);
//举个例子，在 prerequisites 列表中有一个元素 [1, 0]，意味着课程 1 的先修课程是课程 0。那么在 edges 字典中，edges[0]
//就是存储了依赖于课程 0 的所有课程的列表。而在这一行代码中，就将课程 1 的编号添加到了 edges[0] 对应的列表中，表示课程 1 依赖于课程 0
}
for(int i = 0; i<numCourses &&valid; ++i)
{
if(!visited[i])
{
dfs(i);
}
}
return valid;
}
};
python版本
class Solution:
#它接受两个参数：`numCourses`表示课程总数，`prerequisites`是一个二维列表，表示课程之间的先修关系。函数返回一个布尔值，表示是否能够完成所有课程
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
edges = collections.defaultdict(list) #导入Python的collections模块，用于创建默认字典使得在后续添加元素时不需要手动创建空列表。
visited = [0] * numCourses #创建了一个长度为`numCourses`的列表`visited`用于标记课程的访问状态，初始值都为0。
result = list()#创建一个空列表`result`，用于存储访问过的课程的结果
valid = True #表示当前的课程安排是否有效，默认为True。
#将课程之间的依赖关系添加到`edges`中
for info in prerequisites:
edges[info[1]].append(info[0])#表示先修课程info[1] 是 现在课程info[0] 的先修课程,把现在的课程添加到先修课程的edges中
def dfs(u:int):
#在函数内部使用`nonlocal valid`来声明`valid`变量为非局部变量，以便在内部函数中修改外部函数的变量
nonlocal valid
visited[u] = 1#首先标记当前课程为已访问状态（1），然后对当前课程的所有依赖课程进行遍历
for v in edges[u]:
if visited[v] == 0:
dfs(v)#如果依赖课程未被访问过，则递归调用`dfs`函数
if not valid:
return
elif visited[v] == 1:# 如果依赖课程正在被访问中（标记为1），表示存在环路，将`valid`设为False，并直接返回
valid = False
return
visited[u] = 2
result.append(u)#遍历完所有依赖课程后，将当前课程标记为已完成状态（2），并将其添加到结果列表中
for i in range(numCourses):
if valid and not visited[i]:
dfs(i)
return valid
1.2广搜
先学C1, 为0直接加入队列中
C3和C8都包含C1的入度，-1，C8加入队列中（学完一门课后更新入度，为0加入队列）
有向有环图无法执行
方法一的深度优先搜索是一种「逆向思维」:最先被放入栈中的节点是在拓扑排序中最后面的节点。我们也可以使用正向思维，顺序地生成拓扑排序，这种方法也更加直观。
我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。
如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，，直到答案中包含所有的节点(得到了一种拓扑排序)或者不存在没有入边的节点(图中包含环)
上面的想法类似于广度优先搜索，因此我们可以将广度优先搜索的流程与拓扑排序的求解联系起来。
c++版本
//广搜
class Solution{
private:
vector<vector<int>> edges; //这个列表存储了依赖于当前课程的先修课程的所有课程的编号
vector<int> indeg; //一个一维向量，用于表示课程的入度（即指向该课程的边的数量）
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
edges.resize(numCourses);
indeg.resize(numCourses);
for(const auto & info:prerequisites)
{
//根据输入的先修课程信息，构建课程之间的依赖关系，并更新课程的入度
edges[info[1]].push_back(info[0]); //这个列表存储了依赖于当前课程的先修课程info[1]的所有课程info[0]的编号
++indeg[info[0]];//增加现在课程的入度
}
queue<int> q;//队列q
for(int i = 0;i<numCourses;++i)
{
if(indeg[i] == 0)//如果入度为0
{
q.push(i);//直接push到队列中
}
}
int visited = 0;
while (!q.empty())
{
++visited;
int u = q.front();
q.pop();
for(int v:edges[u])
{
--indeg[v];
if(indeg[v] == 0)
{
q.push(v);
}
}
}
return visited == numCourses;
}
};
