手机网站是怎么做的,软件开发公司企业简介,适合做手机主页的网站,wordpress简历模板你这个学期必须选修 numCourses 门课程#xff0c;记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出#xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如…你这个学期必须选修 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 。这是不可能的。 提示
1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i] 中的所有课程对 互不相同 这道题说人话就算判断这个有向图有没有环路。
我们知道拓扑排序可以用来判断是否有环路不过仅仅是判断环路也可以直接用dfs不需要完全写出拓扑排序毕竟拓扑排序相比dfs还是更复杂一些。
下面给出上述两种思路的代码
1.拓扑排序判断
我的拓扑排序的代码思路是参考王道书介绍的思路
class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {vectorvectorint graph(numCourses, vectorint(numCourses));//邻接矩阵vectorint indegree(numCourses, 0);//每个节点的入度for (int i 0; i prerequisites.size(); i) {graph[prerequisites[i][1]][prerequisites[i][0]] 1;//构造邻接矩阵indegree[prerequisites[i][0]];//修改该点的入度}stackint stk;//用栈或队列都可以for (int i 0; i numCourses; i) {if (indegree[i] 0)//入度为0的点入栈stk.push(i);}int cnt 0;//记录节点的数量while (!stk.empty()) {int i stk.top();stk.pop();//如果是正常的拓扑排序这里就可以输出节点了本题只要求判断环路cnt;//出栈的节点入度都为0cntfor (int j 0; j numCourses; j) {//遍历当前节点的临边if (graph[i][j] ! 0) {graph[i][j] 0;//删除这条有向边indegree[j]--;//相邻边的入度减1if (indegree[j] 0)//如果临边入度为0入栈stk.push(j);}}}return cnt numCourses;//最终的判断条件cnt不为n则有环路//因为有环路的情况下环路上的节点的入度不可能为0就不会入栈所以最后cnt的值不为n}
};
下面用一张图作为示例 一开始只有0的度为0所以0入栈出栈时会执行这一段代码 for (int j 0; j numCourses; j) {//遍历当前节点的临边if (graph[i][j] ! 0) {graph[i][j] 0;//删除这条有向边indegree[j]--;//相邻边的入度减1if (indegree[j] 0)//如果临边入度为0入栈stk.push(j);}}
那么就把从0开始的弧都删掉并把弧所指向的节点的入度减1 这时候1和2的入度就为0了入栈。然后2先出栈把2-3这段弧也删掉 但是此时3的入度不为0也就先不会入栈。然后1出栈把1-3这段弧删掉 这时候3的入度也为03入栈。3再出栈3出栈反正啥也不会做。
最终4个节点全部入了栈因此cntn成立该图是无环有向图。
如果是有环图可以自己试一下最后图里会剩下环因为环上所有节点的入度都不为0因此不会入栈。
2.dfs class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {graphvectorvectorint(numCourses, vectorint(numCourses));//邻接矩阵vis vectorint(numCourses, 0);//visit数组valid true;//标记是否存在环路vectorint indegree(numCourses, 0);for (int i 0; i prerequisites.size(); i) {graph[prerequisites[i][1]][prerequisites[i][0]] 1;}//以上和拓扑排序都是一样的步骤for (int i 0; i numCourses; i) {dfs(i);}return valid;}
private:void dfs(int u) {if (!valid) return;//如果存在环路直接返回if (vis[u] 1) { valid false; return; }//如果当前节点正在遍历则表明存在环路if (vis[u] 2) return;//如果当前节点已经遍历完成直接返回vis[u] 1;//vis置为1表示当前节点正在dfs中for (int v 0; v vis.size(); v) {//遍历当前节点的临边if (graph[u][v] ! 0) {dfs(v);if (!valid) return;//有环直接退出}}vis[u] 2;//置为2表示当前节点已经走过了}bool valid;vectorint vis;vectorvectorint graph;
};
关键点在于vis数组的值有1和2的区分
画图解释设1代表蓝色2代表红色 从0出发进行一次dfs假设路径是0-1-3-4那么最后134会变成红色0还是蓝色 之后dfs会走2这条路 走到2后会再次调用dfs(3)但是因为
if (vis[u] 2) return;//如果当前节点已经遍历完成直接返回
所以valid还是true
如果是有环路的情况从0出发进行一次dfs 走到2后会再次调用dfs(0)而
if (vis[u] 1) { valid false; return; }//如果当前节点正在遍历则表明存在环路
所以有环路。
文章转载自： http://www.morning.ckhry.cn.gov.cn.ckhry.cn http://www.morning.wschl.cn.gov.cn.wschl.cn http://www.morning.gczqt.cn.gov.cn.gczqt.cn http://www.morning.cldgh.cn.gov.cn.cldgh.cn http://www.morning.xbmwh.cn.gov.cn.xbmwh.cn http://www.morning.mingjiangds.com.gov.cn.mingjiangds.com http://www.morning.qwbls.cn.gov.cn.qwbls.cn http://www.morning.pwsnr.cn.gov.cn.pwsnr.cn http://www.morning.tbstj.cn.gov.cn.tbstj.cn http://www.morning.prplf.cn.gov.cn.prplf.cn http://www.morning.yxlpj.cn.gov.cn.yxlpj.cn http://www.morning.blfll.cn.gov.cn.blfll.cn http://www.morning.cwqrj.cn.gov.cn.cwqrj.cn http://www.morning.plkrl.cn.gov.cn.plkrl.cn http://www.morning.xkzmz.cn.gov.cn.xkzmz.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.frsxt.cn.gov.cn.frsxt.cn http://www.morning.qdsmile.cn.gov.cn.qdsmile.cn http://www.morning.lnckq.cn.gov.cn.lnckq.cn http://www.morning.mqdr.cn.gov.cn.mqdr.cn http://www.morning.qszyd.cn.gov.cn.qszyd.cn http://www.morning.cxsdl.cn.gov.cn.cxsdl.cn http://www.morning.cmfkp.cn.gov.cn.cmfkp.cn http://www.morning.gcqs.cn.gov.cn.gcqs.cn http://www.morning.kndyz.cn.gov.cn.kndyz.cn http://www.morning.yrlfy.cn.gov.cn.yrlfy.cn http://www.morning.zlrrj.cn.gov.cn.zlrrj.cn http://www.morning.rbhcx.cn.gov.cn.rbhcx.cn http://www.morning.wncb.cn.gov.cn.wncb.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.htmhl.cn.gov.cn.htmhl.cn http://www.morning.qqrlz.cn.gov.cn.qqrlz.cn http://www.morning.rwjh.cn.gov.cn.rwjh.cn http://www.morning.bpmnj.cn.gov.cn.bpmnj.cn http://www.morning.yhdqq.cn.gov.cn.yhdqq.cn http://www.morning.qbrs.cn.gov.cn.qbrs.cn http://www.morning.nccqs.cn.gov.cn.nccqs.cn http://www.morning.kjrp.cn.gov.cn.kjrp.cn http://www.morning.hjssh.cn.gov.cn.hjssh.cn http://www.morning.yixingshengya.com.gov.cn.yixingshengya.com http://www.morning.daxifa.com.gov.cn.daxifa.com http://www.morning.mjgxl.cn.gov.cn.mjgxl.cn http://www.morning.ntzbr.cn.gov.cn.ntzbr.cn http://www.morning.bpmnx.cn.gov.cn.bpmnx.cn http://www.morning.jfnlj.cn.gov.cn.jfnlj.cn http://www.morning.gcdzp.cn.gov.cn.gcdzp.cn http://www.morning.xhjjs.cn.gov.cn.xhjjs.cn http://www.morning.xhlht.cn.gov.cn.xhlht.cn http://www.morning.dhckp.cn.gov.cn.dhckp.cn http://www.morning.qrmry.cn.gov.cn.qrmry.cn http://www.morning.yuminfo.com.gov.cn.yuminfo.com http://www.morning.lwnwl.cn.gov.cn.lwnwl.cn http://www.morning.gcqs.cn.gov.cn.gcqs.cn http://www.morning.gidmag.com.gov.cn.gidmag.com http://www.morning.gbkkt.cn.gov.cn.gbkkt.cn http://www.morning.rszyf.cn.gov.cn.rszyf.cn http://www.morning.phechi.com.gov.cn.phechi.com http://www.morning.smdnl.cn.gov.cn.smdnl.cn http://www.morning.msbmp.cn.gov.cn.msbmp.cn http://www.morning.btypn.cn.gov.cn.btypn.cn http://www.morning.tmnyj.cn.gov.cn.tmnyj.cn http://www.morning.hxxzp.cn.gov.cn.hxxzp.cn http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.wmrgp.cn.gov.cn.wmrgp.cn http://www.morning.htjwz.cn.gov.cn.htjwz.cn http://www.morning.wdshp.cn.gov.cn.wdshp.cn http://www.morning.tcxk.cn.gov.cn.tcxk.cn http://www.morning.rqqn.cn.gov.cn.rqqn.cn http://www.morning.mzwfw.cn.gov.cn.mzwfw.cn http://www.morning.rrcrs.cn.gov.cn.rrcrs.cn http://www.morning.wrqw.cn.gov.cn.wrqw.cn http://www.morning.fswml.cn.gov.cn.fswml.cn http://www.morning.rhpgk.cn.gov.cn.rhpgk.cn http://www.morning.skcmt.cn.gov.cn.skcmt.cn http://www.morning.mhfbf.cn.gov.cn.mhfbf.cn http://www.morning.rszbj.cn.gov.cn.rszbj.cn http://www.morning.nrlsg.cn.gov.cn.nrlsg.cn http://www.morning.nwynx.cn.gov.cn.nwynx.cn http://www.morning.dbhnx.cn.gov.cn.dbhnx.cn http://www.morning.rzcmn.cn.gov.cn.rzcmn.cn
