educative.io

Educative

Simpler solution

It seems there is a simpler solution that the one provided. Why so much complexity?

from collections import deque

class Vertex:
  children = []
  def __init__(self, value):
    self.value = value
    
def topological_sort(vertices, edges):
  sortedOrder = []
  vertices = [None for _ in range(vertices)]
  
  for parent, child in edges:
    if vertices[parent] is None:
      vertices[parent] = Vertex(parent)
    if vertices[child] is None:
      vertices[child] = Vertex(child)
    
    vertices[parent].children.append(vertices[child])

  queue = deque()
  queue.append(vertices[-1])
  
  seen = {}
  while queue:
    vertex = queue.popleft()
    sortedOrder.append(vertex.value)
    for child in vertex.children:
      if child.value not in seen:
        seen[child.value] = True
        queue.append(child)
  
  return sortedOrder

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6010387461832704

Hi @Demos! It seems to me your code doesn’t work in the third example. It returns

[6, 4, 2, 3, 0, 1]

but 3 is a parent of 2.

It also doesn’t work in simpler examples, like topological_sort(2, [[0, 1]])

Expected :[0, 1]
Actual   :[1, 1]

Hope this helps in your learning!