from collections import deque

def can_finish(num_courses, prerequisites):
    counter = 0
    if num_courses <= 0:
        return True

    # a. Initialize the graph
    # count of incoming prerequisites
    inDegree = {i: 0 for i in range(num_courses)}
    graph = {i: [] for i in range(num_courses)}  # adjacency list graph

    # b. Build the graph
    for edge in prerequisites:
        parent, child = edge[1], edge[0]
        graph[parent].append(child)  # put the child into it's parent's list
        inDegree[child] += 1  # increment child's inDegree

    # c. Find all sources i.e., all num_courses with 0 in-degrees
    sources = deque()
    for key in inDegree:
        if inDegree[key] == 0:
            sources.append(key)

    # d. For each source, increment the counter and subtract one from
    # all of its children's in-degrees
    # if a child's in-degree becomes zero, add it to the sources queue
    while sources:
        course = sources.popleft()
        counter += 1 
        # get the node's children to decrement their in-degrees
        for child in graph[course]:
            inDegree[child] -= 1
            if inDegree[child] == 0:
                sources.append(child)

    # topological sort is not possible if the counter is not equal to num_courses
    return counter == num_courses
    
# Driver code
def main():

    prereq = [
              [[1, 0], [2, 1]],
              [[1, 0], [0, 1]],
              [[1, 0], [2, 1], [3, 2], [4, 3]],
              [[1, 0], [2, 1], [3, 2], [4, 3], [0, 4]],
              [[2, 0], [2, 1], [3, 2], [4, 2], [3, 1]]
            ]
    courses = [3, 2, 10, 5, 5]
    for i in range(len(courses)):
        print((i + 1), ".\tNumber of courses: ", courses[i], sep="")
        print("\tNumber of pre-requisites: ", prereq[i])
        print("\tOutput: ", can_finish(courses[i], prereq[i]))
        print('-'*100)


if __name__ == "__main__":
    main()