""" Implementation of [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview/m25rBmwLV00)
"""
from collections import deque


def topological_sort(vertices, edges):
    sortedOrder = []
    if not vertices: return sortedOrder 

    # a. Initialize the graph for sources and incoming degree
    in_degree = {i:0 for i in range(vertices)}  # count of incoming edges
    graph = {i: [] for i in range(vertices)}  # adjacency list graph

    # b. build the graph
    for edge in edges:
        parent, child = edge[0], edge[1]
        graph[parent].append(child)  # put the child into its parent list
        in_degree[child] += 1  # increase the incoming degree counter
    
    # c. find all sources i.e. all vertices with 0 in-degree
    sources = deque()
    for key in in_degree:
        if in_degree[key] == 0:
            sources.append(key)

    # d. for each source, addd it to the sortedOrder and 
    # subtract one from all of its children's in-degree
    # if a child's in-degree becomes zero, add it to the sources queue
    while sources:
        vertex = sources.popleft()
        sortedOrder.append(vertex)
        for child in graph[vertex]:
            in_degree[child] -= 1
            if in_degree[child] == 0:
                sources.append(child)
    
    # topological sort is not possible as the graph has a cycle
    if len(sortedOrder) != vertices:
        return []
    return sortedOrder


if __name__ == "__main__":
    print("Topological sort: " +
        str(topological_sort(4, [[3, 2], [3, 0], [2, 0], [2, 1]])))
    print("Topological sort: " +
        str(topological_sort(5, [[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]])))
    print("Topological sort: " +
        str(topological_sort(7, [[6, 4], [6, 2], [5, 3], [5, 4],
                                 [3, 0], [3, 1], [3, 2], [4, 1]])))