注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex207 Course Schedule  

2015-05-24 20:57:10|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

There are a total of n courses you have to take, labeled from de style="box-sizing: border-box; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px; color: rgb(199, 37, 78); border-radius: 4px; background-color: rgb(249, 242, 244);" >0de> to de style="box-sizing: border-box; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px; color: rgb(199, 37, 78); border-radius: 4px; background-color: rgb(249, 242, 244);" >n - 1de>.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: de style="box-sizing: border-box; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px; color: rgb(199, 37, 78); border-radius: 4px; background-color: rgb(249, 242, 244);" >[0,1]de>

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:
  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.

    Show Tags


    这个需要用到一个关于拓扑排序的算法,计算关于图的入度的问题。举个例子
    ex207 Course Schedule - HT - HT·生活
     
    上面的图中有两个图,对于A,先找入度为0的节点,也就是节点0 ,拿掉他,1和2节点的入度就变成0了,然后依次拿掉1和2,这样节点3的入度也是0了。最终所有节点的入度都是0,这样这个图就是可以拓扑排序的,也就是我们这里课程表的问题。对于图B,可以看到所有的节点入度都是1,构成了环,所以不能拓扑排序,如果,课程设计成这样的话,肯定是不能完成的。这就是拓扑排序算法的简单描述,实现的时候要用一个队列,Node[i]一个维度存入度,一个维度存需要他作为前提条件的label,如下

    struct Node{
    int in; //第一个维度表示她的入度
    vector<int>request; //第二维度存需要“我”的节点
    };

    class Solution {
    public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<Node>nodes(numCourses); //有多少门课程就有多少个节点
    int len = 0;
    len = prerequisites.size();
    int i;
    for (i = 0; i < numCourses; i++)
    nodes[i].in = 0;
    pair<int,int> current;
    for (i = 0; i < len; i++)
    {
    //prerequisites的维数其实是二维的
    current = prerequisites[i];
    nodes[current.second].request.push_back(current.first);
    //nodes[i]的req属性里面存的是需要i的节点,不要搞反了
    nodes[current.first].in++;//入度 +1
    }
    queue<int> myQ;
    for (i = 0; i < numCourses; i++)
    {
    if (nodes[i].in == 0)
    {
    myQ.push(i);
    }
    }
    int index;
    while (!myQ.empty())
    {
    index = myQ.front();
    myQ.pop();
    len = nodes[index].request.size(); //需要index节点的课程都存在这里的request里面
    for (i = 0; i < len; i++)
    {
    //这里挨个把需要index节点课程的入度都 -1
    nodes[nodes[index].request[i]].in--;
    if (nodes[nodes[index].request[i]].in == 0)
    myQ.push(nodes[index].request[i]);
    }
    }
    for (i = 0; i < numCourses; i++)
    {
    //最后检查时候还有入度大于0的课程
    if (nodes[i].in > 0)
    return false;
    }
    return true;
    }
    };



      评论这张
     
    阅读(23)| 评论(0)
    推荐 转载

    历史上的今天

    评论

    <#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
     
     
     
     
     
     
     
     
     
     
     
     
     
     

    页脚

    网易公司版权所有 ©1997-2017