先修课程按数组

我们知道拓扑排序可以用来判断是否有环路不过仅仅是判断环路也可以直接用dfs不需要完全写出拓扑排序毕竟拓扑排序相比dfs还是更复杂一些。

1.拓扑排序判断

vectorint(numCourses));//邻接矩阵vectorint

indegree(numCourses,

{graph[prerequisites[i][1]][prerequisites[i][0]]

1;//构造邻接矩阵indegree[prerequisites[i][0]];//修改该点的入度}stackint

(int

stk.top();stk.pop();//如果是正常的拓扑排序这里就可以输出节点了本题只要求判断环路cnt;//出栈的节点入度都为0cntfor

(int

0;//删除这条有向边indegree[j]--;//相邻边的入度减1if

(indegree[j]

0)//如果临边入度为0入栈stk.push(j);}}}return

cnt

numCourses;//最终的判断条件cnt不为n则有环路//因为有环路的情况下环路上的节点的入度不可能为0就不会入栈所以最后cnt的值不为n}

下面用一张图作为示例

0;//删除这条有向边indegree[j]--;//相邻边的入度减1if

(indegree[j]

这时候1和2的入度就为0了入栈。

然后2先出栈把2-3这段弧也删掉

但是此时3的入度不为0也就先不会入栈。

然后1出栈把1-3这段弧删掉

如果是有环图可以自己试一下最后图里会剩下环因为环上所有节点的入度都不为0因此不会入栈。

2.dfs

{graphvectorvectorint(numCourses,

vectorint(numCourses));//邻接矩阵vis

0);//visit数组valid

{graph[prerequisites[i][1]][prerequisites[i][0]]

(int

return;//如果当前节点已经遍历完成直接返回vis[u]

(int

从0出发进行一次dfs假设路径是0-1-3-4那么最后134会变成红色0还是蓝色

之后dfs会走2这条路