Kahn's algorithms to arrange CouseScheduleCalculating strongly-connected components in a directed graph using DFSSorting AlgorithmsSort Algorithms in JuliaLeetcode 210. Course Schedule IIFind Eulerian Tour Algorithm - with multithreading and random permutations“The Story of a Tree” solved using depth-first searchtopological sorting to find the pre-requisite for coursesGenerating maze for complicated Hunt the Wumpus gameHash table solution to twoSumthe memory usage to “CourseSchedule” algorithms

Getting extremely large arrows with tikzcd

How could indestructible materials be used in power generation?

How do I exit BASH while loop using modulus operator?

Why do I get negative height?

How obscure is the use of 令 in 令和?

What's the meaning of "Sollensaussagen"?

How dangerous is XSS

In Bayesian inference, why are some terms dropped from the posterior predictive?

Is it a bad idea to plug the other end of ESD strap to wall ground?

Was the old ablative pronoun "med" or "mēd"?

Finitely generated matrix groups whose eigenvalues are all algebraic

Why didn't Boeing produce its own regional jet?

What does the same-ish mean?

Why is the sentence "Das ist eine Nase" correct?

Did 'Cinema Songs' exist during Hiranyakshipu's time?

How can I deal with my CEO asking me to hire someone with a higher salary than me, a co-founder?

How to stretch the corners of this image so that it looks like a perfect rectangle?

GFCI outlets - can they be repaired? Are they really needed at the end of a circuit?

Is it possible to map the firing of neurons in the human brain so as to stimulate artificial memories in someone else?

Processor speed limited at 0.4 Ghz

Placement of More Information/Help Icon button for Radio Buttons

Are British MPs missing the point, with these 'Indicative Votes'?

Car headlights in a world without electricity

How can saying a song's name be a copyright violation?



Kahn's algorithms to arrange CouseSchedule


Calculating strongly-connected components in a directed graph using DFSSorting AlgorithmsSort Algorithms in JuliaLeetcode 210. Course Schedule IIFind Eulerian Tour Algorithm - with multithreading and random permutations“The Story of a Tree” solved using depth-first searchtopological sorting to find the pre-requisite for coursesGenerating maze for complicated Hunt the Wumpus gameHash table solution to twoSumthe memory usage to “CourseSchedule” algorithms













0












$begingroup$


I wrote a solution to Course Schedule II - LeetCode




There are a total of n courses you have to take, labeled from 0 to n-1.



Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]



Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.



There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.



Example 1:



Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished



Example 2:



Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation:
There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .


Note:



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

  2. You may assume that there are no duplicate edges in the input prerequisites.



my solution



class Solution:
def findOrder(self,numCourses, prerequirements):
"""
:type numCourse: int
:type prerequirements: List[List[int]]
:rtype:bool
"""
#if not prerequirements: return True
# if numCourses == None and len(prerequirements) == 0: return True

L = []

in_degrees = [ 0 for _ in range(numCourses)] #index as node
#graph = [[]] * numCourses
graph = [[] for _ in range(numCourses)]

#Construct the graph
for u, v in prerequirements:
graph[v].append(u) #index as node
in_degrees[u] += 1
logging.debug(f"graph: graph")
logging.debug(f"in_degrees in_degrees")
#
Q = [i for i in range(len(in_degrees)) if in_degrees[i]==0] #collect nodes without pre-edges
logging.debug(f"Q: Q")

while Q: #while Q is not empty
start = Q.pop()#remove a node from Q
L.append(start) #add n to tail of L
logging.debug(f"L: L")

for v in graph[start]:#for each node v with a edge e
in_degrees[v] -= 1 #remove edge
if in_degrees[v] == 0:
Q.append(v)
logging.debug(f"indegree: in_degrees")
#check there exist a cycle
for i in range(len(in_degrees)): #if graph has edge
if in_degrees[i] > 0:
return []
logging.debug(f"L: L")
return L


TestCase:



class MyCase(unittest.TestCase):
def setUp(self):
self.solution1 = Solution()
self.solution2 = Solution2()

def test_bfs1(self):
numCourse = 2
prerequirements = [[1,0]]
check = self.solution1.findOrder(numCourse, prerequirements)
logging.debug(f"check")
answer = [0, 1]
self.assertEqual(check, answer)


def test_bfs2(self):
numCourse = 4
prerequirements = [[1,0],[2,0],[3,1],[3,2]]
check = self.solution1.findOrder(numCourse, prerequirements)
logging.debug(f"check")
answer = [[0,1,2,3], [0,2,1,3]]
self.assertIn(check, answer)


def test_bfs3(self):
numCourse = 2
prerequirements = []
check = self.solution1.findOrder(numCourse, prerequirements)
logging.debug(f"check")
answer = [1,0]
self.assertEqual(check, answer)


def test_bfs4(self):
numCourse = 2
prerequirements = [[0,1],[1,0]]
check = self.solution1.findOrder(numCourse, prerequirements)
logging.debug(f"check")
answer = []
self.assertEqual(check, answer)


Get a low score




Runtime: 56 ms, faster than 57.28% of Python3 online submissions for Course Schedule II.
Memory Usage: 14 MB, less than 51.41% of Python3 online submissions for Course Schedule II.










share









$endgroup$
















    0












    $begingroup$


    I wrote a solution to Course Schedule II - LeetCode




    There are a total of n courses you have to take, labeled from 0 to n-1.



    Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]



    Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.



    There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.



    Example 1:



    Input: 2, [[1,0]] 
    Output: [0,1]
    Explanation: There are a total of 2 courses to take. To take course 1 you should have finished



    Example 2:



    Input: 4, [[1,0],[2,0],[3,1],[3,2]]
    Output: [0,1,2,3] or [0,2,1,3]
    Explanation:
    There are a total of 4 courses to take. To take course 3 you should have finished both
    courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
    So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .


    Note:



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

    2. You may assume that there are no duplicate edges in the input prerequisites.



    my solution



    class Solution:
    def findOrder(self,numCourses, prerequirements):
    """
    :type numCourse: int
    :type prerequirements: List[List[int]]
    :rtype:bool
    """
    #if not prerequirements: return True
    # if numCourses == None and len(prerequirements) == 0: return True

    L = []

    in_degrees = [ 0 for _ in range(numCourses)] #index as node
    #graph = [[]] * numCourses
    graph = [[] for _ in range(numCourses)]

    #Construct the graph
    for u, v in prerequirements:
    graph[v].append(u) #index as node
    in_degrees[u] += 1
    logging.debug(f"graph: graph")
    logging.debug(f"in_degrees in_degrees")
    #
    Q = [i for i in range(len(in_degrees)) if in_degrees[i]==0] #collect nodes without pre-edges
    logging.debug(f"Q: Q")

    while Q: #while Q is not empty
    start = Q.pop()#remove a node from Q
    L.append(start) #add n to tail of L
    logging.debug(f"L: L")

    for v in graph[start]:#for each node v with a edge e
    in_degrees[v] -= 1 #remove edge
    if in_degrees[v] == 0:
    Q.append(v)
    logging.debug(f"indegree: in_degrees")
    #check there exist a cycle
    for i in range(len(in_degrees)): #if graph has edge
    if in_degrees[i] > 0:
    return []
    logging.debug(f"L: L")
    return L


    TestCase:



    class MyCase(unittest.TestCase):
    def setUp(self):
    self.solution1 = Solution()
    self.solution2 = Solution2()

    def test_bfs1(self):
    numCourse = 2
    prerequirements = [[1,0]]
    check = self.solution1.findOrder(numCourse, prerequirements)
    logging.debug(f"check")
    answer = [0, 1]
    self.assertEqual(check, answer)


    def test_bfs2(self):
    numCourse = 4
    prerequirements = [[1,0],[2,0],[3,1],[3,2]]
    check = self.solution1.findOrder(numCourse, prerequirements)
    logging.debug(f"check")
    answer = [[0,1,2,3], [0,2,1,3]]
    self.assertIn(check, answer)


    def test_bfs3(self):
    numCourse = 2
    prerequirements = []
    check = self.solution1.findOrder(numCourse, prerequirements)
    logging.debug(f"check")
    answer = [1,0]
    self.assertEqual(check, answer)


    def test_bfs4(self):
    numCourse = 2
    prerequirements = [[0,1],[1,0]]
    check = self.solution1.findOrder(numCourse, prerequirements)
    logging.debug(f"check")
    answer = []
    self.assertEqual(check, answer)


    Get a low score




    Runtime: 56 ms, faster than 57.28% of Python3 online submissions for Course Schedule II.
    Memory Usage: 14 MB, less than 51.41% of Python3 online submissions for Course Schedule II.










    share









    $endgroup$














      0












      0








      0





      $begingroup$


      I wrote a solution to Course Schedule II - LeetCode




      There are a total of n courses you have to take, labeled from 0 to n-1.



      Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]



      Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.



      There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.



      Example 1:



      Input: 2, [[1,0]] 
      Output: [0,1]
      Explanation: There are a total of 2 courses to take. To take course 1 you should have finished



      Example 2:



      Input: 4, [[1,0],[2,0],[3,1],[3,2]]
      Output: [0,1,2,3] or [0,2,1,3]
      Explanation:
      There are a total of 4 courses to take. To take course 3 you should have finished both
      courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
      So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .


      Note:



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

      2. You may assume that there are no duplicate edges in the input prerequisites.



      my solution



      class Solution:
      def findOrder(self,numCourses, prerequirements):
      """
      :type numCourse: int
      :type prerequirements: List[List[int]]
      :rtype:bool
      """
      #if not prerequirements: return True
      # if numCourses == None and len(prerequirements) == 0: return True

      L = []

      in_degrees = [ 0 for _ in range(numCourses)] #index as node
      #graph = [[]] * numCourses
      graph = [[] for _ in range(numCourses)]

      #Construct the graph
      for u, v in prerequirements:
      graph[v].append(u) #index as node
      in_degrees[u] += 1
      logging.debug(f"graph: graph")
      logging.debug(f"in_degrees in_degrees")
      #
      Q = [i for i in range(len(in_degrees)) if in_degrees[i]==0] #collect nodes without pre-edges
      logging.debug(f"Q: Q")

      while Q: #while Q is not empty
      start = Q.pop()#remove a node from Q
      L.append(start) #add n to tail of L
      logging.debug(f"L: L")

      for v in graph[start]:#for each node v with a edge e
      in_degrees[v] -= 1 #remove edge
      if in_degrees[v] == 0:
      Q.append(v)
      logging.debug(f"indegree: in_degrees")
      #check there exist a cycle
      for i in range(len(in_degrees)): #if graph has edge
      if in_degrees[i] > 0:
      return []
      logging.debug(f"L: L")
      return L


      TestCase:



      class MyCase(unittest.TestCase):
      def setUp(self):
      self.solution1 = Solution()
      self.solution2 = Solution2()

      def test_bfs1(self):
      numCourse = 2
      prerequirements = [[1,0]]
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = [0, 1]
      self.assertEqual(check, answer)


      def test_bfs2(self):
      numCourse = 4
      prerequirements = [[1,0],[2,0],[3,1],[3,2]]
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = [[0,1,2,3], [0,2,1,3]]
      self.assertIn(check, answer)


      def test_bfs3(self):
      numCourse = 2
      prerequirements = []
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = [1,0]
      self.assertEqual(check, answer)


      def test_bfs4(self):
      numCourse = 2
      prerequirements = [[0,1],[1,0]]
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = []
      self.assertEqual(check, answer)


      Get a low score




      Runtime: 56 ms, faster than 57.28% of Python3 online submissions for Course Schedule II.
      Memory Usage: 14 MB, less than 51.41% of Python3 online submissions for Course Schedule II.










      share









      $endgroup$




      I wrote a solution to Course Schedule II - LeetCode




      There are a total of n courses you have to take, labeled from 0 to n-1.



      Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]



      Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.



      There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.



      Example 1:



      Input: 2, [[1,0]] 
      Output: [0,1]
      Explanation: There are a total of 2 courses to take. To take course 1 you should have finished



      Example 2:



      Input: 4, [[1,0],[2,0],[3,1],[3,2]]
      Output: [0,1,2,3] or [0,2,1,3]
      Explanation:
      There are a total of 4 courses to take. To take course 3 you should have finished both
      courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
      So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .


      Note:



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

      2. You may assume that there are no duplicate edges in the input prerequisites.



      my solution



      class Solution:
      def findOrder(self,numCourses, prerequirements):
      """
      :type numCourse: int
      :type prerequirements: List[List[int]]
      :rtype:bool
      """
      #if not prerequirements: return True
      # if numCourses == None and len(prerequirements) == 0: return True

      L = []

      in_degrees = [ 0 for _ in range(numCourses)] #index as node
      #graph = [[]] * numCourses
      graph = [[] for _ in range(numCourses)]

      #Construct the graph
      for u, v in prerequirements:
      graph[v].append(u) #index as node
      in_degrees[u] += 1
      logging.debug(f"graph: graph")
      logging.debug(f"in_degrees in_degrees")
      #
      Q = [i for i in range(len(in_degrees)) if in_degrees[i]==0] #collect nodes without pre-edges
      logging.debug(f"Q: Q")

      while Q: #while Q is not empty
      start = Q.pop()#remove a node from Q
      L.append(start) #add n to tail of L
      logging.debug(f"L: L")

      for v in graph[start]:#for each node v with a edge e
      in_degrees[v] -= 1 #remove edge
      if in_degrees[v] == 0:
      Q.append(v)
      logging.debug(f"indegree: in_degrees")
      #check there exist a cycle
      for i in range(len(in_degrees)): #if graph has edge
      if in_degrees[i] > 0:
      return []
      logging.debug(f"L: L")
      return L


      TestCase:



      class MyCase(unittest.TestCase):
      def setUp(self):
      self.solution1 = Solution()
      self.solution2 = Solution2()

      def test_bfs1(self):
      numCourse = 2
      prerequirements = [[1,0]]
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = [0, 1]
      self.assertEqual(check, answer)


      def test_bfs2(self):
      numCourse = 4
      prerequirements = [[1,0],[2,0],[3,1],[3,2]]
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = [[0,1,2,3], [0,2,1,3]]
      self.assertIn(check, answer)


      def test_bfs3(self):
      numCourse = 2
      prerequirements = []
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = [1,0]
      self.assertEqual(check, answer)


      def test_bfs4(self):
      numCourse = 2
      prerequirements = [[0,1],[1,0]]
      check = self.solution1.findOrder(numCourse, prerequirements)
      logging.debug(f"check")
      answer = []
      self.assertEqual(check, answer)


      Get a low score




      Runtime: 56 ms, faster than 57.28% of Python3 online submissions for Course Schedule II.
      Memory Usage: 14 MB, less than 51.41% of Python3 online submissions for Course Schedule II.








      python algorithm





      share












      share










      share



      share










      asked 6 mins ago









      AliceAlice

      2484




      2484




















          0






          active

          oldest

          votes












          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "196"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216760%2fkahns-algorithms-to-arrange-couseschedule%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          0






          active

          oldest

          votes








          0






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes















          draft saved

          draft discarded
















































          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216760%2fkahns-algorithms-to-arrange-couseschedule%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

          Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

          Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar