Problem:
Topological Sort   A directed acyclic graph (DAG) can be used to represent the ordering of tasks. Tasks are represented by vertices and constraints where one task can begin before another, are represented by edges. For example, in the above example, you can undertake task B after both task A and task B are finished. You can obtain the proper sequence of all the tasks by a topological sort. Given a DAG $G$, print the order of vertices after the topological sort. Input A directed graph $G$ is given in the following format: $|V|\;|E|$ $s_0 \; t_0$ $s_1 \; t_1$ : $s_{|E|-1} \; t_{|E|-1}$   $|V|$ is the number of vertices and $|E|$ is the number of edges in the graph. The graph vertices are named with the numbers $0, 1,..., |V|-1$ respectively. $s_i$ and $t_i$ represent source and target nodes of $i$-th edge (directed). Output Print the vertices numbers in order. Print a number in a line. If there are multiple possible solutions, print any one of them (the solution is judged by a special validator). Constraints  $1 \leq |V| \leq 10,000$  $0 \leq |E| \leq 100,000$  There are no parallel edges in $G$  There are no self loops in $G$  Sample Input 6 6
0 1
1 2
3 1
3 4
4 5
5 2 Sample Output 0
3
1
4
5
2

Solution (Python):



from collections import namedtuple


DirectedEdge = namedtuple('DirectedEdge', ('src', 'dest'))


def revert(edge):
    return edge._replace(src=edge.dest, dest=edge.src)


class Digraph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e

    def reversed(self):
        g = self.__class__(self.v)
        for e in self.edges():
            g.add(revert(e))

        return g


def sorted_topological(graph):
    return reversed(list(reverse_post(graph.reversed())))


def reverse_post(graph):
    def visit(v):
        if not visited[v]:
            visited[v] = True
            return True
        else:
            return False

    def leave(v):
        if not left[v]:
            left[v] = True
            vs.append(v)
        return False

    visited = [False] * graph.v
    left = [False] * graph.v
    vs = []

    for i in range(graph.v):
        if not visited[i]:
            stack = [(i, leave)]
            stack.extend((e.dest, visit) for e in graph.adj(i))
            while stack:
                v, f = stack.pop()
                if f(v):
                    stack.append((v, leave))
                    for e in graph.adj(v):
                        stack.append((e.dest, visit))
    return reversed(vs)


def run():
    v, e = [int(i) for i in input().split()]
    g = Digraph(v)

    for _ in range(e):
        s, t = [int(i) for i in input().split()]
        g.add(DirectedEdge(s, t))

    for v in sorted_topological(g):
        print(v)


if __name__ == '__main__':
    run()

Solution (Python):



from collections import namedtuple


DirectedEdge = namedtuple('DirectedEdge', ('src', 'dest'))


def revert(edge):
    return edge._replace(src=edge.dest, dest=edge.src)


class Digraph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e

    def reversed(self):
        g = self.__class__(self.v)
        for e in self.edges():
            g.add(revert(e))

        return g


def sorted_topological(graph):
    return reverse_post(graph)


def reverse_post(graph):
    def visit(v):
        if not visited[v]:
            visited[v] = True
            return True
        else:
            return False

    def leave(v):
        if not left[v]:
            left[v] = True
            vs.append(v)
        return False

    visited = [False] * graph.v
    left = [False] * graph.v
    vs = []

    for i in range(graph.v):
        if not visited[i]:
            stack = [(i, leave)]
            stack.extend((e.dest, visit) for e in graph.adj(i))
            while stack:
                v, f = stack.pop()
                if f(v):
                    stack.append((v, leave))
                    for e in graph.adj(v):
                        stack.append((e.dest, visit))
    return reversed(vs)


def run():
    v, e = [int(i) for i in input().split()]
    g = Digraph(v)

    for _ in range(e):
        s, t = [int(i) for i in input().split()]
        g.add(DirectedEdge(s, t))

    for v in sorted_topological(g):
        print(v)


if __name__ == '__main__':
    run()

Solution (Python):
from collections import deque





def topologicalSortBfs(n):
    for i in range(n):
        color[i] = WHITE

    for i in range(0, n):
        if indeg[i] == 0 and color[i] == WHITE:
            bfs(i)


def bfs(s):
    Q.appendleft(s)
    color[s] = GRAY
    while Q:
        u = Q.popleft()

        out.append(u)

        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and color[v] == WHITE:
                color[v] = GRAY
                Q.append(v)


def topologicalSortDfs(n):
    for i in range(n):
        color[i] = WHITE

    for s in range(0, n):
        if color[s] == WHITE:
            dfs(s)


def dfs(u):
    color[u] = GRAY
    for v in G[u]:
        if color[v] == WHITE:
            dfs(v)
    out.appendleft(u)


n, e = map(int, input().split())
G = {}
for i in range(n):
    G[i] = []
indeg = [0] * n
for i in range(e):
    s, t = map(int, input().split())
    indeg[t] += 1
    G[s].append(t)
color = [None] * n
out = deque([])
WHITE = 0
GRAY = 1
Q = deque([])

topologicalSortDfs(n)
print(*out)

Solution (Python):


import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')


def topological_sort(N: int, edges: list) -> list:
    
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(edges)):
        
        incnts[edges[i][1]] += 1
        
        outnodes[edges[i][0]].append(edges[i][1])
    
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    
    L = []
    
    while S:
        
        L.append(S.pop())
        
        for node in outnodes[L[-1]]:
            
            incnts[node] -= 1
            
            if incnts[node] == 0:
                S.add(node)
    
    return L

N,M=MAP()
edges=[None]*M
for i in range(M):
    s,t=MAP()
    edges[i]=(s, t)

ans=topological_sort(N, edges)
for i in range(N):
    print(ans[i])

Solution (Python):
from sys import exit
import queue
V,E = [int(n) for n in input().split()]
ans = []


graph = [[] for _ in range(V)]
indeg = [0]*V
yet = [True]*V
def bfs(s):
    q = queue.Queue()
    q.put(s)
    while(not q.empty()):
        u = q.get()
        ans.append(u)
        yet[u]=False
        for v in graph[u]:
            indeg[v]-=1
            if(indeg[v]==0):
                q.put(v)

for i in range(E):
    s, t = [int(n) for n in input().split()]
    graph[s].append(t)
    indeg[t]+=1
for i in range(V):
    if(indeg[i]==0 and yet[i]):
        bfs(i)
for a in ans:
    print(a)

Solution (Python):
from collections import deque, defaultdict

def topological_sort(V, E):
    '''
    Kahn's Algorithm (O(|V| + |E|) time)
    Input:
    V = [0, 1, ..., N-1]: a list of vertices of the digraph
    E: the adjacency list of the digraph (dict)
    Output:
    If the input digraph is acyclic, then return a topological sorting of the digraph.
    Else, return None.
    '''
    indeg = {v: 0 for v in V}
    for ends in E.values():
        for v in ends:
            indeg[v] += 1
    
    q = deque([v for v in V if indeg[v] == 0])
    top_sorted = []
    while q:
        v = q.popleft()
        top_sorted.append(v)
        
        for u in E[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    if len(top_sorted) == len(V): 
        return top_sorted
    else: 
        return None

N, M = map(int, input().split())
V = range(N)
E = defaultdict(list)
for _ in range(M):
    s, t = map(int, input().split())
    E[s].append(t)
print(*topological_sort(V, E), sep='\n')

Solution (Python):
from collections import Counter
from collections import deque
def topological_sort(g, v):
    in_count = Counter(y for x in g.values() for y in x)
    s = deque([i for i in range(v) if in_count[i] == 0])
    while s:
        n = s.popleft()
        yield n
        for m in g[n]:
            in_count[m] -= 1
            if in_count[m] <= 0:
                s.append(m)

from sys import stdin
from collections import defaultdict
readline = stdin.readline

v, e = map(int, readline().split())
g = defaultdict(set)
for _ in range(e):
    s, t = map(int, readline().split())
    g[s] |= {t}
for i in topological_sort(g, v):
    print(i)

Solution (Python):
def bfs(s):
    que = [s]
    used[s] = True
    while que:
        u = que.pop(0)
        ans.append(u)

        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and not used[v]:
                used[v] = True
                que.append(v)

def tsort():
    for u in xrange(V):
        if indeg[u] == 0 and not used[u]:
            bfs(u)

V, E = map(int, raw_input().split())
indeg = [0] * V
used = [False] * V
G = [[] for i in xrange(V)]
ans = []

for i in xrange(E):
    s, t = map(int, raw_input().split())
    indeg[t] += 1
    G[s].append(t)

tsort()
for i in ans:
    print i

Solution (Python):
def tsort(G):
    def bfs(s):
        que = [s]
        used[s] = True
        while que:
            u = que.pop(0)
            res.append(u)

            for v in G[u]:
                indeg[v] -= 1
                if indeg[v] == 0 and not used[v]:
                    used[v] = True
                    que.append(v)

    indeg = [0] * V
    used = [False] * V
    res = []
    for u in xrange(V):
        for v in G[u]:
            indeg[v] += 1
    for u in xrange(V):
        if indeg[u] == 0 and not used[u]:
            bfs(u)
    return res


V, E = map(int, raw_input().split())
G = [[] for i in xrange(V)]
for i in xrange(E):
    s, t = map(int, raw_input().split())
    G[s].append(t)

ans = tsort(G)
for i in ans:
    print i

Solution (Python):
from collections import deque

def Topologicalsort():
    for i in xrange(v):
        if indeg[i]==0 and color[i]==0:
            bfs(i)

def bfs(s):
    color[s]=2
    q.append(s)
    while len(q)>0:
        i=q.popleft()
        ans.append(i)
        for j in m[i]:
            indeg[j]-=1
            if indeg[j]==0  and color[j]==0:
                q.append(j)
                color[j]=1

v,e=map(int,raw_input().split())
m=[[]for i in xrange(v)]
indeg=[0]*v
color=[0]*v
ans=deque()
q=deque()
for i in xrange(e):
    s,t=map(int,raw_input().split())
    m[s].append(t)
    indeg[t]+=1
Topologicalsort()
for i in ans:
    print(i)

Solution (Python):
import sys

sys.setrecursionlimit(200000)


def dfs(i):
    global visited, edges, counter, finish_order
    visited[i] = True
    for edge in edges[i]:
        if visited[edge]:
            continue
        dfs(edge)
    finish_order[i] = (counter, i)
    counter += 1


n, m = map(int, input().split())

edges = [set() for _ in range(n)]

for _ in range(m):
    s, t = map(int, input().split())
    edges[s].add(t)

visited = [False] * n
finish_order = [None] * n
counter = 0

for i in range(n):
    if not visited[i]:
        dfs(i)

for d, i in sorted(finish_order, reverse=True):
    print(i)

Solution (Python):
from collections import deque
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
deg = [0]*V
for i in xrange(E):
    s, t = map(int, raw_input().split())
    g[s].append(t)
    deg[t] += 1

ans = list(v for v in xrange(V) if deg[v]==0)
deq = deque(ans)
used = [0]*V

while deq:
    v = deq.popleft()
    for t in g[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)
print "\n".join(map(str, ans))

Solution (Python):



import array
import collections


class TopologicalSortError(Exception):
    pass


def topological_sort(num_vs, adj_vs):
    in_deg = array.array("L", (0 for _ in range(num_vs)))
    for dests in adj_vs:
        for dest in dests:
            in_deg[dest] += 1
    visited = array.array("B", (False for _ in range(num_vs)))
    sorted_vs = array.array("L")
    for s in range(num_vs):
        if in_deg[s] == 0 and not visited[s]:
            q = collections.deque()
            q.append(s)
            visited[s] = True
            while q:
                u = q.popleft()
                sorted_vs.append(u)
                for v in adj_vs[u]:
                    in_deg[v] -= 1
                    if in_deg[v] == 0 and not visited[v]:
                        visited[v] = True
                        q.append(v)
    if all(x == 0 for x in in_deg):
        return sorted_vs
    else:
        raise TopologicalSortError("The graph has a cycle")


def main():
    v, e = map(int, input().split())
    adj_vs = [set() for _ in range(v)]
    for _ in range(e):
        s, t = map(int, input().split())
        adj_vs[s].add(t)
    for u in topological_sort(v, adj_vs):
        print(u)


if __name__ == '__main__':
    main()

Solution (Python):


import array
import heapq


def topological_sort(num_vs, adj_vs):
    """ Performs topological sorting of the given DAG.

    This function computes the lexicographically least
    topological order of the given DAG.

    :param num_vs int: The number of vertices.
    :param adj_vs list: The adjacency list.
    :return: The lexicographically least topological order.
    :rtype: :obj:`array.array`
    :raises TopologicalSortError: if the given graph is not a DAG
    """
    in_deg = array.array("L", (0 for _ in range(num_vs)))
    for dests in adj_vs:
        for dest in dests:
            in_deg[dest] += 1
    sorted_vs = array.array("L")
    pq = []
    for s in range(num_vs):
        if in_deg[s] == 0:
            heapq.heappush(pq, s)
    while pq:
        u = heapq.heappop(pq)
        sorted_vs.append(u)
        for v in adj_vs[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                heapq.heappush(pq, v)
    if all(x == 0 for x in in_deg):
        return sorted_vs
    else:
        raise TopologicalSortError("The graph has a cycle")


def main():
    v, e = map(int, input().split())
    adj_vs = [set() for _ in range(v)]
    for _ in range(e):
        s, t = map(int, input().split())
        adj_vs[s].add(t)
    for u in topological_sort(v, adj_vs):
        print(u)


if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque

def Topologicalsort(n):     
    start=deque()
    for i in xrange(n):
        if indeg[i]==0 :
            start.append(i)
    while len(start)>0:
        i=start.popleft()
        ans.append(i)
        for j in g[i]:
            indeg[j]-=1
            if indeg[j]==0:
                start.append(j)
    return ans

v,e=map(int,raw_input().split())
g=[[]for i in xrange(v)]
indeg=[0]*v
ans=[]
for i in xrange(e):
    s,t=map(int,raw_input().split())
    g[s].append(t)
    indeg[t]+=1
    
ans=Topologicalsort(v)
for i in ans:
    print(i)

Solution (Python):
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj_list = [[] for i in range(V)]

is_visited = [False] * V

indeg = [0] * V

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj_list[s].append(t)
    indeg[t] += 1

import collections

Q = collections.deque()
out = collections.deque()


def bfs(s):
    Q.append(s)
    is_visited[s] = True
    while Q:
        u = Q.popleft()

        out.append(u)

        for v in adj_list[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and is_visited[v] == False:
                is_visited[v] = True
                Q.append(v)



for u in range(V):
    if indeg[u] == 0 and is_visited[u] == False:
        bfs(u)

print(*out, sep = '\n')

Solution (Python):
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj_list = [[] for i in range(V)]

is_visited = [False] * V

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj_list[s].append(t)

import collections

out = collections.deque()

def dfs(u):
    is_visited[u] = True
    for v in adj_list[u]:
        if not is_visited[v]:
            dfs(v)
    out.appendleft(u)

for s in range(V):
    if not is_visited[s]:
        dfs(s)

print(*out, sep = '\n')

Solution (Python):



from sys import stdin
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(_v_info, _input_adj_table, _in_deg_list):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        _input_adj_table[v_from].append(v_to)
        _in_deg_list[v_to] += 1
    return _input_adj_table, _in_deg_list


def topological_sort():
    for v in range(vertices):
        if not in_deg_list[v] and status[v] is UNVISITED:
            bfs(v)

    return ans


def bfs(v):
    v_queue.append(v)
    status[v] = VISITED_IN_QUEUE

    while v_queue:
        current = v_queue.popleft()

        ans.append(current)

        for v_adj in adj_table[current]:
            in_deg_list[v_adj] -= 1
            if not in_deg_list[v_adj] and status[v_adj] is UNVISITED:
                status[v_adj] = VISITED_IN_QUEUE
                v_queue.appendleft(v_adj)

        status[current] = POPPED_OUT

    return None


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    status = [UNVISITED] * vertices
    v_queue = deque()
    init_adj_table = tuple([] for _ in range(vertices))
    init_in_deg_list = [0] * vertices

    ans = []
    adj_table, in_deg_list = generate_adj_matrix(v_info, init_adj_table, init_in_deg_list)
    print(*topological_sort())

Solution (Python):



from sys import stdin
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        init_in_deg_list[v_to] += 1
    return init_adj_table, init_in_deg_list


def topological_sort():
    for v in range(vertices):
        if not in_deg_list[v] and status[v] is UNVISITED:
            bfs(v)

    return ans


def bfs(v):
    v_queue.append(v)
    status[v] = VISITED_IN_QUEUE

    while v_queue:
        current = v_queue.popleft()

        ans.append(current)

        for v_adj in adj_table[current]:
            in_deg_list[v_adj] -= 1
            if not in_deg_list[v_adj] and status[v_adj] is UNVISITED:
                status[v_adj] = VISITED_IN_QUEUE
                v_queue.appendleft(v_adj)

        status[current] = POPPED_OUT

    return None


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    status = [UNVISITED] * vertices
    v_queue = deque()
    init_adj_table = tuple([] for _ in range(vertices))
    init_in_deg_list = [0] * vertices

    ans = []
    adj_table, in_deg_list = generate_adj_matrix(v_info)
    print(*topological_sort())

Solution (Python):



from sys import stdin
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        init_in_deg_list[v_to] += 1
    return init_adj_table, init_in_deg_list


def topological_sort():
    for v in range(vertices):
        if not in_deg_list[v] and status[v] is UNVISITED:
            bfs(v)

    return ans


def bfs(v):
    v_queue.append(v)
    status[v] = VISITED_IN_QUEUE

    while v_queue:
        current = v_queue.popleft()

        ans.append(current)

        for v_adj in adj_table[current]:
            in_deg_list[v_adj] -= 1
            if not in_deg_list[v_adj] and status[v_adj] is UNVISITED:
                status[v_adj] = VISITED_IN_QUEUE
                v_queue.appendleft(v_adj)

        status[current] = POPPED_OUT

    return None


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    status = [UNVISITED] * vertices
    v_queue = deque()
    init_adj_table = tuple([] for _ in range(vertices))
    init_in_deg_list = [0] * vertices

    ans = []
    adj_table, in_deg_list = generate_adj_matrix(v_info)
    print(*topological_sort(), sep='\n')

Solution (Python):



"""

input:
6 6
0 1
1 2
3 1
3 4
4 5
5 2

output:
0
3
1
4
5
2
"""

from sys import stdin
from collections import deque

UNVISITED, VISITED_IN_QUEUE, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        init_in_deg_list[v_to] += 1
    return init_adj_table, init_in_deg_list


def topological_sort():
    for v in range(vertices):
        if not in_deg_list[v] and status[v] is UNVISITED:
            bfs(v)
    return ans


def bfs(v):
    queue = deque()

    queue.append(v)
    status[v] = VISITED_IN_QUEUE

    while queue:
        current = queue.popleft()
        ans.append(current)

        for v_adj in adj_table[current]:
            in_deg_list[v_adj] -= 1
            if not in_deg_list[v_adj] and status[v_adj] is UNVISITED:
                status[v_adj] = VISITED_IN_QUEUE
                queue.appendleft(v_adj)

        status[current] = POPPED_OUT

    return None


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])

    status = [UNVISITED] * vertices
    init_adj_table = tuple([] for _ in range(vertices))
    init_in_deg_list = [0] * vertices

    ans = []
    adj_table, in_deg_list = generate_adj_matrix(v_info)
    print(*topological_sort(), sep='\n')

Solution (Python):
import queue

nv, ne = map(int, input().split(' '))
in_degs = [0] * nv
q = queue.Queue()
outs = {}
o = []

for _ in range(ne):
    s, t = map(int, input().split(' '))

    if s in outs: outs[s].append(t)
    else: outs[s] = [t]

    in_degs[t] += 1

for i in range(nv):
    if in_degs[i] == 0: q.put(i)

while not q.empty():
    v = q.get()
    o.append(v)

    if v in outs:
        for out in outs[v]:
            in_degs[out] -= 1
            if in_degs[out] == 0: q.put(out)

[print(v) for v in o]

Solution (Python):
nv, ne = map(int, input().split(' '))
in_degs = [0] * nv
q = []
outs = {}
o = []

for _ in range(ne):
    s, t = map(int, input().split(' '))

    if s in outs: outs[s].append(t)
    else: outs[s] = [t]

    in_degs[t] += 1

for i in range(nv):
    if in_degs[i] == 0: q.append(i)

while len(q) > 0:
    v = q.pop(0)
    o.append(v)

    if v in outs:
        for out in outs[v]:
            in_degs[out] -= 1
            if in_degs[out] == 0: q.append(out)

[print(v) for v in o]

Solution (Python):
nv, ne = map(int, input().split(' '))
in_degs = [0] * nv
q = []
outs = {}
o = []

for _ in range(ne):
    s, t = map(int, input().split(' '))

    if s in outs: outs[s].append(t)
    else: outs[s] = [t]

    in_degs[t] += 1

for i in range(nv):
    if in_degs[i] == 0: q.append(i)

while q:
    v = q.pop(0)
    o.append(v)

    if v in outs:
        for out in outs[v]:
            in_degs[out] -= 1
            if in_degs[out] == 0: q.append(out)

[print(v) for v in o]

Solution (Python):


import sys
import os
import pprint
from queue import Queue

"""Topological Sort"""




V, E = list(map(int, input().split()))
G = [[] for i in range(V)]
indig = [0] * V 
for i in range(E):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    indig[t] += 1

q = Queue()
out = []

def bfs(node_index):
    q.put(node_index)

    while not q.empty():
        u = q.get()
        out.append(u)

        
        for index in G[u]:
            indig[index] -= 1
            if indig[index] == 0:
                q.put(index)


indig_copy = indig[:]
for i in range(V):
    if indig_copy[i] == 0:
        bfs(node_index=i)

for v in out:
    print(v)

Solution (Python):
V,E = map(int, input().split())
adj = [[] for _ in range(V)]
for _ in range(E):
    s,t = map(int, input().split())
    adj[s].append(t)

color = [0 for _ in range(V)]
topo = []

def topo_dfs(s):
    color[s] = 1
    if adj[s]:
        for next in adj[s]:
            if color[next] == 0:
                topo_dfs(next)
    topo.append(s)
    return

for i in range(V):
    if color[i] == 0:
        topo_dfs(i)
print("\n".join(map(str, topo[::-1])))

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    indegrees = [0 for i in range(nvertices)]
    adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        s, t = map(int, input().split())
        adj[s].append(t)
        indegrees[t] += 1

    S = []
    for i in range(nvertices):
        if indegrees[i] == 0:
            S.append(i)
    ordering = []
    while S:
        u = S.pop(0)
        ordering.append(u)
        for v in adj[u]:
            indegrees[v] -= 1
            if indegrees[v] == 0:
                S.append(v)

    for v in ordering:
        print(v)


main()

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        s, t = map(int, input().split())
        Adj[s].append(t)

    visited = [False] * nvertices
    ordering = []
    for u in range(nvertices):
        if not visited[u]:
            dfs(u, Adj, visited, ordering)

    for v in reversed(ordering):
        print(v)


def dfs(u, Adj, visited, ordering):
    visited[u] = True
    for v in Adj[u]:
        if not visited[v]:
            dfs(v, Adj, visited, ordering)
    ordering.append(u)


main()

Solution (Python):
from sys import stdin
from collections import deque
n, e = map(int, stdin.readline().split())
G = [[] for _ in [0] * n]
indeg = [0] * n
out = []
V = [False] * n
def bfs(s):
    dq = deque([s])
    V[s] = True
    while dq:
        u = dq.popleft()
        out.append(u)
        for i in range(len(G[u])):
            v = G[u][i]
            indeg[v] -= 1
            if indeg[v] == 0 and not V[v]:
                V[v] = True
                dq.append(v)
def tsort():
    for u in range(n):
        for i in range(len(G[u])):
            indeg[G[u][i]] += 1
    for u in range(n):
        if indeg[u] == 0 and not V[u]:
            bfs(u)
    for i in range(len(out)):
        print(out[i])
for _ in [0] * e:
    s, t = map(int, stdin.readline().split())
    G[s].append(t)
tsort()

Solution (Python):
from sys import stdin
from collections import deque
n, e = map(int, stdin.readline().split())
G = [[] for _ in [0] * n]
indeg = [0] * n
out = []
V = [False] * n
def bfs(s):
    dq = deque([s])
    V[s] = True
    while dq:
        u = dq.popleft()
        out.append(u)
        for i in range(len(G[u])):
            v = G[u][i]
            indeg[v] -= 1
            if indeg[v] == 0 and not V[v]:
                V[v] = True
                dq.append(v)
def tsort():
    for u in range(n):
        for i in range(len(G[u])):
            indeg[G[u][i]] += 1
    for u in range(n):
        if indeg[u] == 0 and not V[u]:
            bfs(u)
    print(*out, sep='\n')
for _ in [0] * e:
    s, t = map(int, stdin.readline().split())
    G[s].append(t)
tsort()

Solution (Python):
from sys import stdin
from collections import deque
V, E = map(int, stdin.readline().split())
adj_list = [[] for _ in [0] * V]
is_visited = [False] * V
for _ in [0] * E:
    s, t = map(int, stdin.readline().split())
    adj_list[s].append(t)
out = deque()
def dfs(u):
    is_visited[u] = True
    for v in adj_list[u]:
        if not is_visited[v]:
            dfs(v)
    out.appendleft(u)
for s in range(V):
    if not is_visited[s]:
        dfs(s)
print(*out, sep='\n')

Solution (Python):
from sys import stdin
from collections import deque
V, E = map(int, stdin.readline().split())
adj_list = deque([[] for _ in [0] * V])
is_visited = [False] * V
for _ in [0] * E:
    s, t = map(int, stdin.readline().split())
    adj_list[s].append(t)
out = deque()
def dfs(u):
    is_visited[u] = True
    for v in adj_list[u]:
        if not is_visited[v]:
            dfs(v)
    out.appendleft(u)
for s in range(V):
    if not is_visited[s]:
        dfs(s)
print(*out, sep='\n')

Solution (Python):
from sys import stdin
from collections import deque
V, E = map(int, stdin.readline().split())
adj_list = [[] for _ in [0] * V]
is_visited = [False] * V
for _ in [0] * E:
    s, t = map(int, stdin.readline().split())
    adj_list[s].append(t)
out = deque()
def dfs(u):
    is_visited[u] = True
    for v in adj_list[u]:
        if not is_visited[v]:
            dfs(v)
    out.appendleft(u)
for s in range(V):
    if not is_visited[s]:
        dfs(s)
print(*out, sep='\n')

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    Adj = [[] * nvertices for i in range(nvertices)]
    for i in range(nedges):
        u, v = map(int, input().split())
        Adj[u].append(v)

    visited = [False] * nvertices
    ordering = []
    for u in range(nvertices):
        if not visited[u]:
            dfs(Adj, u, visited, ordering)

    for u in reversed(ordering):
        print(u)


def dfs(Adj, u, visited, ordering):
    visited[u] = True
    for v in Adj[u]:
        if not visited[v]:
            dfs(Adj, v, visited, ordering)

    ordering.append(u)


main()

Solution (Python):
def topological_sort(G, revG):
  n = len(revG)
  S = set()
  for u in revG:
    if len(revG[u]) == 0:
      S.add(u)
  L = []
  while len(S) > 0:
    u = S.pop()
    L.append(u)
    for v in G[u]:
      revG[v].remove(u)
      if len(revG[v]) == 0:
        S.add(v)
  return L


n, m = [int(i) for i in input().strip().split(' ')]
G = {}
revG = {}
for i in range(n):
  G[i] = set()
  revG[i] = set()
for _ in range(m):
  s, t = [int(i) for i in input().strip().split(' ')]
  G[s].add(t)
  revG[t].add(s)


L = topological_sort(G, revG)
for n in L:
  print(n)

Solution (Python):

import collections

V, E = map(int, input().split())
Adj_list = [[] for _ in range(V)]
isVisited = [False] * V

for i in range(E):
    u, v = map(int, input().split())
    Adj_list[u].append(v)

Out = collections.deque()


def DFS(u):
    isVisited[u] = True
    for v in Adj_list[u]:
        if isVisited[v] != True:
            DFS(v)
    Out.appendleft(u)

for i in range(V):
    if isVisited[i] != True:
        DFS(i)
        
print(*Out, sep = '\n')

Solution (Python):
import collections

V, E = map(int, input().split())
Adj_list = [[] for _ in range(V)]
Indeg = [0] * V 
isVisited = [False] * V
ans = []

for i in range(E):
    u, v = map(int, input().split())
    Adj_list[u].append(v)
    Indeg[v] += 1

def BFS(u):
    dq = collections.deque()
    dq.append(u)
    isVisited[u] = True
    
    while dq:
        v = dq.popleft()
        ans.append(v)
        
        for s in Adj_list[v]:
            Indeg[s] -= 1
            if Indeg[s] == 0 and isVisited[s] != True:
                isVisited[s] = True
                dq.append(s)
    return ans

for i in range(V):
    if Indeg[i] == 0 and isVisited[i] != True:
        BFS(i)

for i in ans:
    print(i)