Skip to content

Instantly share code, notes, and snippets.

@Algogator
Last active September 29, 2020 13:12
Show Gist options
  • Save Algogator/6b3b07806df65027e433ccc102892bad to your computer and use it in GitHub Desktop.
Save Algogator/6b3b07806df65027e433ccc102892bad to your computer and use it in GitHub Desktop.
Topo
# numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
from collections import defaultdict, deque
class Solution:
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
# Prepare the graph
adj_list = defaultdict(list)
indegree = {}
for dest, src in prerequisites:
adj_list[src].append(dest)
# Record each node's in-degree
indegree[dest] = indegree.get(dest, 0) + 1
# Queue for maintainig list of nodes that have 0 in-degree
zero_indegree_queue = deque([k for k in range(numCourses) if k not in indegree])
topological_sorted_order = []
# Until there are nodes in the Q
while zero_indegree_queue:
# Pop one node with 0 in-degree
vertex = zero_indegree_queue.popleft()
topological_sorted_order.append(vertex)
# Reduce in-degree for all the neighbors
if vertex in adj_list:
for neighbor in adj_list[vertex]:
indegree[neighbor] -= 1
# Add neighbor to Q if in-degree becomes 0
if indegree[neighbor] == 0:
zero_indegree_queue.append(neighbor)
return topological_sorted_order if len(topological_sorted_order) == numCourses else []
Initialize a queue, Q to keep a track of all the nodes in the graph with 0 in-degree.
Iterate over all the edges in the input and create an adjacency list and also a map of node v/s in-degree.
Add all the nodes with 0 in-degree to Q.
The following steps are to be done until the Q becomes empty.
Pop a node from the Q. Let's call this node, N.
For all the neighbors of this node, N, reduce their in-degree by 1. If any of the nodes' in-degree reaches 0, add it to the Q.
Add the node N to the list maintaining topologically sorted order.
Continue from step 4.1.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment