#!/usr/bin/env python
# coding: utf-8

# In[1]:


from collections import deque
def topologicalOrdering(g):
    
    # find indegrees of each node
    out = reduce(lambda a,b: a+b, g.values())
    indegrees = {}
    for node in set(out + g.keys()):
        if node not in out:
            indegrees[node] = 0
        else:
            indegrees[node] = out.count(node)

    # collect set of all nodes in graph with zero indegrees
    candidates = deque()
    for node in indegrees:
        if indegrees[node] == 0:
            candidates.appendleft(node)

    L = [] # list for order of nodes
    
    # choose zero indegree node and remove it from graph
    while candidates:
        a = candidates.pop()
        L.append(a)
        if a in g:
            for b in g[a]:
                indegrees[b] -= 1
                if indegrees[b] == 0:
                    candidates.appendleft(b)           
    
    #if graph has edges that have not been removed/if there is a cycle
    for node in indegrees:
        if indegrees[node] != 0:
            return "the input graph is not a DAG"
    else:
        return L


# In[2]:


graph = {1:[2], 2:[3], 4:[2], 5:[3]}
topologicalOrdering(graph)


# In[70]:


g = dict()
f = open('input/rosalind_ba5n.txt', 'r')
for line in f:
    line = line.strip().split('->')
    g[int(line[0])] = map(int,line[1].split(','))
print topologicalOrdering(g)


# In[3]:


g = {'a': ['b', 'c', 'd', 'e', 'f'],
    'b': ['c', 'f'],
    'c': ['d'],
    'd': [], 
    'e': ['d', 'f'],
    'f': []}
topologicalOrdering(g)


# In[ ]: