educative.io

No need for hashMap, space complexity can be O(v)

Courses
,
#1

We can use the same logic, but we use int[] array to store indegree.

// time: O(V + E)
// space: O(V)

for example
while (!queue.isEmpty()) {
int pre = queue.poll();
for (int[] pair : prerequisites) {
if (pre == pair[1]) {
indegree[pair[0]]–;
if (indegree[pair[0]] == 0) {
queue.offer(pair[0]);
}
}
}
}

#2

Can you describe more?

You are missing the graph formation. IMO.

Cheers

#3

I agree with you @Gaurav7, it needs the graph formation so it ends with the same space complexity. I used the same approach so here is the full code, in case anybody is interested:

from collections import deque


def topological_sort(vertices, edges):
  incoming = [0 for _ in range(vertices)]
  outgoing = [[] for _ in range(vertices)]
  for p, c in edges:
    incoming[c] += 1
    outgoing[p] += [c]

  sources = deque()
  for i in range(vertices):
    if incoming[i] == 0:
      sources.append(i)

  order = []
  while sources:
    v = sources.popleft()
    order.append(v)
    for e in outgoing[v]:
      incoming[e] -= 1
      if incoming[e] == 0:
        sources.append(e)

  if len(order) != vertices:
    return []
  return order