Как мне сделать мою топологическую сортировку линейной по времени? (Код хорошо аннотирован)

Вопрос 1:

Каким должно быть правильное время работы для хорошо реализованной топологической сортировки. Я вижу разные мнения:

Википедия говорит: O(log^2(n))

Geeksforgeeks говорит: O(V+E)

Вопрос 2:

Моя реализация работает на O(V*E). Потому что в худшем случае мне нужно будет пройти по графу E раз и каждый раз мне нужно будет проверять V элементов. Как мне превратить мою реализацию в линейное время.

Алгоритм работает поэтапно:

1. Создайте граф в виде списка смежности

например этот график

0 - - 2
    \
      1 -- 3

создает этот список смежности

{0: [], 1: [0], 2: [0], 3: [1, 2]}

0 ни от чего не зависит, 1 зависит от 0 и т.д..

2. Перебрать граф и найти узлы, которые не имеют никаких зависимостей

def produce_graph(prerequisites):
    adj = {}
    for course in prerequisites:
        if course[0] in adj:
            # append prequisites
            adj[course[0]].append(course[1])
        else:
            adj[course[0]] = [course[1]]

        # ensure that prerequisites are also in the graph
        if course[1] not in adj:
            adj[course[1]] = []

    return adj

def toposort(graph):
    sorted_courses = []
    while graph:

        # we mark this as False
        # In acyclic graph, we should be able to resolve at least
        # one node in each cycle
        acyclic = False
        for node, predecessors in graph.items():
            # here, we check whether this node has predecessors
            # if a node has no predecessors, it is already resolved,
            # we can jump straight to adding the node into sorted
            # else, mark resolved as False
            resolved = len(predecessors) == 0
            for predecessor in predecessors:
                # this node has predecessor that is not yet resolved
                if predecessor in graph:
                    resolved = False
                    break
                else:
                    # this particular predecessor is resolved
                    resolved = True

            # all the predecessor of this node has been resolved
            # therefore this node is also resolved
            if resolved:
                # since we are able to resolve this node
                # We mark this to be acyclic
                acyclic = True
                del graph[node]
                sorted_courses.append(node)

        # if we go through the graph, and found that we could not resolve
        # any node. Then that means this graph is cyclic
        if not acyclic:
            # if not acyclic then there is no order
            # return empty list
            return []

    return sorted_courses

graph = produce_graph([[1,0],[2,0],[3,1],[3,2]])
print toposort(graph)