Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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



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


Sample output:
0
3
1
4
5
2

Submission status: Wrong Answer

Solution code:
from collections import deque

def Topologicalsort(start):
    for i in start:
        color[i]=2
        q.append(i)
    while len(q)>0:
        i=q.popleft()
        color[i]=2
        ans.append(i)
        for j in xrange(v):
            if m[i][j]!=-1 and color[j]==0:
                if ct[j]>1:
                    ct[j]-=1
                else:
                    q.append(m[i][j])
                    color[j]=1

v,e=map(int,raw_input().split())
m=[[-1]*v for i in xrange(v)]
mr=[[-1]*v for i in xrange(v)]
ct=[0]*v
color=[0]*v
start=[]
ans=deque()
q=deque()
for i in xrange(v):
    s,t=map(int,raw_input().split())
    m[s][t]=t
    mr[t][s]=1
    ct[t]+=1

for i in xrange(v):
    if mr[i]==[-1]*v:
        start.append(i)
Topologicalsort(start)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import pprint
from queue import Queue

"""Topological Sort"""

#fd = os.open('GRL_4_B.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

V, E = list(map(int, input().split()))
G = [[] for i in range(V)]
indig = [0] * V # ??\?¬???°
for i in range(V):
    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)

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

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


print(out)

Submission status: Wrong Answer

Solution code:
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(n):
  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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


# 幅優先と深さ優先でトポロジカルソート
def set_indeg(u):
    # t = uとなる数を求める。
    ans = 0
    for line in G:
        if line[u] == 1:
            ans += 1
    return ans


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

    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 range(n):
            if G[u][v] != 1:
                continue
            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
        indeg[i] = set_indeg(i)

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


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


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

topologicalSortDfs(n)
print(*out)
# 031452
# dfsがおかしい

Submission status: Time Limit Exceeded

Solution code:
import queue

nv, ne = map(int, input().split(' '))
in_degrees = [[] for _ in range(nv)]
q = queue.Queue()
o = []

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

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

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

    for i in range(nv):
        if v in in_degrees[i]:
            in_degrees[i].remove(v)
            if len(in_degrees[i]) == 0: q.put(i)

[print(v) for v in o]

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t = map(int, input().split())
    G[s].append(t)

ans = []
V = set()

def dfs(n):
    for e in G[n]:
        dfs(e)
    if n not in V:
        ans.append(n)
        V.add(n)


for i in range(N):
    if i not in V:
        if i not in V:
            dfs(i)

print(*ans[::-1], sep="\n")

Submission status: Memory Limit Exceeded

Solution code:
from collections import deque


# 幅優先と深さ優先でトポロジカルソート
def set_indeg(u):
    # t = uとなる数を求める。
    ans = 0
    for line in G:
        if line[u] == 1:
            ans += 1
    return ans


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

    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 range(n):
            if G[u][v] != 1:
                continue
            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
        indeg[i] = set_indeg(i)

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


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


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

topologicalSortBfs(n)
print(*out)
# 031452
# dfsがおかしい

Submission status: Memory Limit Exceeded

Solution code:
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 xrange(v):
            if m[i][j]!=-1:
                indeg[j]-=1
                if indeg[j]==0  and color[j]==0:
                    q.append(m[i][j])
                    color[j]=1

v,e=map(int,raw_input().split())
m=[[-1]*v 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][t]=t
    indeg[t]+=1
Topologicalsort()
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# GRL_4_B: Path/Cycle - Topological Sort

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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# GRL_4_B: Path/Cycle - Topological Sort

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()

Submission status: Accepted

Solution code:
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)
# 031452
# dfsがおかしい

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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')

# トポロジカルソート(頂点数、辺集合(DAG, 0-indexed))
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])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            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])

Submission status: Accepted

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

# N = int(input())
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)
# a = [int(input()) for _ in range(N)]
# S = str(input())
# L = len(S)
# T = str(input())
# exit()

Submission status: Accepted

Solution code:
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): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        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')

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# ????????????????????°???????????°????????????????????\??????????????¢?????´???????????¨??????????§???????

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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

def Topologicalsort(n):     #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)

Submission status: Accepted

Solution code:
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)


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

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

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

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())

Submission status: Accepted

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

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())

Submission status: Accepted

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

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')

Submission status: Accepted

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

"""

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')

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
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]