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: Accepted

Solution code:
from collections import deque


def topological_sort(graph: list) -> list:
    """入力した重みなしDAGに対してトポロジカルソートする
    計算量: O(|V|+|E|)
    入力条件: グラフGはDAGである、グラフGに多重辺はない、グラフGに自己ループはない
    """
    n = len(graph)
    degree = [0] * n
    for g in graph:
        for next_pos in g:
            degree[next_pos] += 1
    
    # 次数が0、つまり入力の無い頂点を初期値状態とする
    ans = [i for i in range(n) if degree[i] == 0]

    q = deque(ans)
    while q:
        pos = q.popleft()
        for next_pos in graph[pos]:
            degree[next_pos] -= 1
            if degree[next_pos] == 0:
                q.append(next_pos)
                ans.append(next_pos)
    return ans

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    graph[a].append(b)
ans = topological_sort(graph)
for pos in ans:
    print(pos)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)


def dfs(i: int) -> None:
    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


if __name__ == "__main__":
    V, E = map(int, input().split())
    edges = [set() for _ in range(V)]  # type: ignore

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

    visited = [False] * V
    finish_order = [(0, 0)] * V
    counter = 0

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

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    edge = [[]for _ in range(N)]
    indegree = [0]*N #入次数
    for _ in range(M):
        a,b = MI()
        edge[a].append(b)
        indegree[b] += 1
    #print(indegree)
    #入次数が0の点からあれしていく
    queue = deque() 
    for i,x in enumerate(indegree):
        if not x:
            queue.append(i)

    pop = queue.popleft
    topological_index = []
    while queue:
        v = pop()
        topological_index.append(v)

        for to in edge[v]:
            indegree[to] -= 1
            if not indegree[to]:
                queue.append(to)
    if tuple(1 for i in indegree if i!=0):
        print("loop")

    print(*topological_index,sep="\n")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

v, n = map(int, input().split())  #v:頂点数 n:辺の数
es = [[int(x) for x in input().split()] for _ in range(n)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)

for i in res:
    print(i)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def topological_sort(graph):
    """
    :param list of (list of int) graph:
    :return:
    """
    # 入次数
    ins = [0] * len(graph)
    for vs in graph:
        for v in vs:
            ins[v] += 1

    # 入次数がゼロのやつ
    zeros = []
    for v, cnt in enumerate(ins):
        if cnt == 0:
            zeros.append(v)

    # 入次数がゼロのやつから順に追加してく
    ret = []
    while zeros:
        v = zeros.pop()
        ret.append(v)
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                zeros.append(u)
    return ret


V, E = list(map(int, sys.stdin.readline().split()))
ST = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]

graph = [[] for _ in range(V)]
for s, t in ST:
    graph[s].append(t)

ans = topological_sort(graph)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)
hh = [0]*N
for _ in range(M):
    x,y = inpl()
    lines[x].add(y)
    hh[y] += 1

q = queue.Queue()
for t in range(N):
    if hh[t] == 0:
        q.put(t)

topological = []
while not q.empty():
    s = q.get()
    topological.append(s)
    for t in lines[s]:
        hh[t] -= 1
        if hh[t] == 0:
            q.put(t)

for x in topological:
    print(x)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

def Topo_sort(x,y):
	co = cl.Counter(n for m in x.values() for n in m)
	S = cl.deque([i for i in range(y) if co[i] == 0])
	while S:
		n = S.popleft()
		yield n
		for i in x[n]:
			co[i] -= 1
			if co[i] <= 0:
				S.append(i)
# g = cl.dafaultdict(set)に有向グラフを作成し(g[~] != ~) リストが帰ってくる

v,e = m()

g = cl.defaultdict(set)

for i in range(e):
	s,t = m()
	g[s] |= {t}
a = Topo_sort(g,v)
#print(list(a))
for i in Topo_sort(g,v):
	print(i)

Submission status: Accepted

Solution code:
v, e = map(int, input().split())
indeg = [0]*v
uv = [[] for _ in range(v)]
for i in range(e):
    s, t = map(int, input().split())
    uv[s].append(t)
    indeg[t] += 1

'''
topologicalSort
トポロジカルソート
'''
visited = [False]*v
ans = []
for i in range(v):
    if indeg[i] == 0 and not visited[i]:
        q = [i]
        visited[i] = True
        while len(q) > 0:
            u = q.pop(0)
            ans.append(u)
            for v in uv[u]:
                indeg[v] -= 1
                if indeg[v] == 0 and not visited[v]:
                    visited[v] = True
                    q.append(v)

for v in ans:
    print(v)

Submission status: Accepted

Solution code:
#topologivcal sort

from collections import deque

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

a = [[] for i in range(n)]
in_num = [0]*n
for _ in range(k):
    p, q = map(int, input().split())
    a[p] += [q]
    in_num[q] += 1
# print(a)
# print(in_num)
# a = [[1],[2],[],[1,4],[5],[2]]
# n = len(a)
# in_num = [0, 2, 2, 0, 1, 1]
color = [0]*n
result = deque()
aa = deque()

def topologicalSort_w(s):
    aa.append(s)
    color[s] = 1
    while aa:
#         print(aa)
#         print(in_num)
        u = aa.popleft()
        result.append(u)
        for v in a[u]:
            in_num[v] -= 1
            if in_num[v] == 0 and color[v] == 0:
                color[v] = 1
                aa.append(v)
        

for i in range(n):
    if in_num[i] == 0 and color[i] == 0:
        topologicalSort_w(i)
        

                
for i in range(len(result)):
    print(result.popleft())

Submission status: Accepted

Solution code:
def input(f):
    V, E = map(int, f.readline().split())
    s = [None for _ in range(E)]
    t = [None for _ in range(E)]
    for i in range(E):
        s[i], t[i] = map(int, f.readline().split())
    return V, E, s, t

def solve(V, E, s, t):
    graph = [[] for _ in range(V)]
    for i in range(E):
        graph[s[i]].append(t[i])
    
    order = []
    used = [False for _ in range(V)]
    def visit(cur):
        if used[cur]:
            return
        used[cur] = True
        for nxt in graph[cur]:
            visit(nxt)
        order.append(cur)
    
    for i in range(V):
        visit(i)
    
    for v in reversed(order):
        print(v)

with open('/dev/stdin') as f:
    solve(*input(f))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

# 1:shortest path
# 1_A
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
                print(dist, q)
    return dist

v,e,r = map(int, input().split(" "))
adj = [[] for i in range(v)]
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj[s].append([t, d])
lis = dijkstra(v, r)
print(lis)
for i in lis:
    print(str(i).upper())
"""

# 1_B
"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == num-1:
                        return False
        if not update:
            break
    return dist

v,e,r = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj.append([s, t, d])
lis = bellman_ford(v, r)
if not lis:
    print("NEGATIVE CYCLE")
else:
    for i in lis:
        print(str(i).upper())
"""

# 1_C
"""
def warshallfloyd(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i]+d[i][k])
v,e = map(int, input().split())
d = [[float("inf") for j in range(v)] for i in range(v)]
for i in range(v):
    d[i][i] = 0
for i in range(e):
    s, t, c = map(int, input().split())
    d[s][t] = c
warshallfloyd(v)
for i in range(v):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        quit()
for i in d:
    for j in range(v):
        if j < v-1:
            print(str(i[j]).upper(), end = " ")
        else:
            print(str(i[j]).upper())
"""

# 2:spanning tree
# 2_A
"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
v,e = LI()
c = LIR(e)
c.sort(key = lambda x:x[2])
par = [i for i in range(v)]
rank = [0 for i in range(v)]
k = 0
ans = 0
for a,b,w in c:
    if not same(a,b):
        k += 1
        unite(a,b)
        ans += w
    if k == v-1:
        break
print(ans)
"""

#2_B
"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank(x) < rank(y):
        par[x] = y
    else:
        par[y] = x
        if rank(x) == rank(y):
            rank[x] += 1
"""

#3:connected components
#3_A

#3_B

#3_C


#4:path/cycle
#4_A
"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
            if dist[k] > dist[j] + l:
                dist[k] = dist[j] + l
                update = True
                if i == num-1:
                    return False
        if not update:
            break
    return True

v, e = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t = map(int, input().split(" "))
    adj.append([s, t, -1])
for i in range(v):
    if not bellman_ford(v,i):
        print(1)
        quit()
print(0)
"""

#4_B
def visit(s):
    if f[s]:
        f[s] = 0
        for t in v[s]:
            visit(t)
        l.append(s)
n,e = LI()
v = [[] for i in range(n)]
for i in range(e):
    s,t = LI()
    v[s].append(t)
l = []
f = [1 for i in range(n)]
for i in range(n):
    visit(i)
l = l[::-1]
for i in l:
    print(i)

#5:tree
#5_A
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = II()
adj = [[] for i in range(n)]
for i in range(n-1):
    s,t,w = LI()
    adj[s].append([t, w])
    adj[t].append([s, w])
d = dijkstra(n,0)
i = d.index(max(d))
d2 = dijkstra(n,i)
print(max(d2))
"""

#5_B
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = int(input())
adj = [[] for i in range(n)]
for i in range(n-1):
    s, t, w = map(int, input().split(" "))
    adj[s].append([t, w])
    adj[t].append([s, w])
for i in range(n):
    s = dijkstra(n,i)
    print(max(s))
"""
#5_C

#5_D

#5_E


#6
#6_A_maximum_flow
"""
def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in range(n):
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return [None,0]
    path = [None for i in range(bfs_map[g]+1)]
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in range(n+1):
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return [path,m]

def ford_fulkerson(s,g,c,n):
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return sum(c[g])

n,e = LI()
c = [[0 for i in range(n)] for j in range(n)]
for i in range(e):
    a,b,w = LI()
    if a != n-1:
        c[a][b] = w
print(ford_fulkerson(0,n-1,c,n))
"""
#6_B


#7
#7_A
"""
def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in range(n):
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return [None,0]
    path = [None for i in range(bfs_map[g]+1)]
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in range(n+1):
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return [path,m]

def ford_fulkerson(s,g,c,n):
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return sum(c[g])

x,y,e = LI()
c = [[0 for i in range(x+y+2)] for j in range(x+y+2)]
for i in range(x):
    c[0][i+1] = 1
for i in range(y):
    c[x+i+1][x+y+1] = 1
for i in range(e):
    a,b = LI()
    c[a+1][x+b+1] = 1
print(ford_fulkerson(0,x+y+1,c,x+y+2))
"""

Submission status: Accepted

Solution code:
import heapq
def topologicalsort(N,E):
    V = [0]*N
    for i in range(N):
        for y in E[i]:
            V[y] += 1
    S = [ i for i in range(N) if V[i] == 0]
    SORTED = []
    while S:
        s = S.pop(0)
        SORTED.append(s)
        for t in E[s]:
            V[t] -= 1
            if V[t] == 0:
                S.append(t)
    return SORTED
    
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( int, input().split())
    # x, y = x-1, y-1
    E[x].append(y)
ANS = topologicalsort(N, E)
for i in range(N):
    print(ANS[i])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(int(1e6))

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

edges = {}

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

stack = []
visited = set()


def visit(v):
    if v in visited:
        return
    visited.add(v)
    if v in edges:
        for t in edges[v]:
            visit(t)
    stack.append(v)


for i in range(n):
    visit(i)

while len(stack) > 0:
    print(stack.pop())

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

def read_graph(n, k):
    A = [ [] for _ in range(n) ]
    for _ in range(k):
        line = stdin.readline().strip().split()
        A[int(line[0])].append(int(line[1]))
    return A

def topological_sort(n, A):
    color = ["WHITE"] * n
    Q = deque([])
    out = []

    indeg = [0] * n
    for i in range(n):
        for j in A[i]:
            indeg[j] = indeg[j] + 1

    def bfs(s):
        nonlocal color
        nonlocal indeg
        nonlocal Q
        color[s] = "GRAY"
        Q.append(s)

        while Q:
            u = Q.popleft()
            out.append(u)

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

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

    return out

n, k = [int(i) for i in input().split()]
A = read_graph(n, k)
B = topological_sort(n, A)
for i in B:
    print(i)

Submission status: Accepted

Solution code:
V,E=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(E)]

#Tarjanのアルゴリズム

from collections import deque
QUE = deque(list(range(V)))
EDGEOUTLIST=[[] for i in range(V)]

for x,y in EDGE:
    EDGEOUTLIST[x].append(y)

check=[0]*V
TOP_SORT=[]

def dfs(x):
    if check[x]==1:
        return
    
    for to in EDGEOUTLIST[x]:
        if check[to]==0:
            dfs(to)

    TOP_SORT.append(x)
    check[x]=1

while QUE:
    x=QUE.pop()
    dfs(x)

TOP_SORT.reverse()
for v in TOP_SORT:
    print(v)

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, id):
        self.id = id
        self.adj = []
        self.indeg = 0
        self.passed = False

    def is_start(self):
        return self.indeg == 0

    def __repr__(self):
        return "Node({},{},{},{})".format(
            self.id, self.passed,
            [v.id for v in self.adj],
            [v.id for v in self.radj])


def read_edges(ne, V):
    for _ in range(ne):
        s, t = [int(x) for x in input().split()]
        V[s].adj.append(V[t])
        V[t].indeg += 1


def sort(V):
    W = []

    def visit(v):
        S = []
        S.append(v)

        while S:
            v = S.pop()
            v.passed = True
            W.append(v)
            for a in v.adj:
                a.indeg -= 1
                if a.is_start():
                    S.append(a)

    for v in V:
        if v.is_start() and not v.passed:
            visit(v)

    return W


def main():
    nv, ne = [int(x) for x in input().split()]
    V = [Node(id) for id in range(nv)]
    read_edges(ne, V)
    W = sort(V)
    [print(v.id) for v in W]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


V,E = map(int,input().split())

in_num = [0]*V
G = [[] for i in range(V)]

for loop in range(E):
    tmp_from,tmp_to = map(int,input().split())
    G[tmp_from].append(tmp_to)
    in_num[tmp_to] += 1

Q = deque()

for i in range(V):
    if in_num[i] == 0:
        Q.append(i)

while len(Q) > 0:
    node_id = Q.popleft()
    print("%d"%(node_id))
    for adj in G[node_id]:
        in_num[adj] -= 1
        if in_num[adj] == 0:
            Q.append(adj)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s, g, color, indeg, out):
    q = deque()
    q.append(s)
    color[s] = True
    while len(q) != 0:
        u = q.popleft()
        out.append(u)
        for i in range(len(g[u])):
            v = g[u][i]
            indeg[v] -= 1
            if indeg[v] == 0 and not color[v]:
                color[v] = True
                q.append(v)


def tsort(n, g):
    color = [False] * n
    indeg = [0] * n
    for u in range(n):
        for i in range(len(g[u])):
            v = g[u][i]
            indeg[v] += 1

    out = []
    for u in range(n):
        if indeg[u] == 0 and not color[u]:
            bfs(u, g, color, indeg, out)

    for line in out:
        print(line)


if __name__ == '__main__':
    n, m = [int(v) for v in input().split()]
    g = [[] for i in range(n)]
    for i in range(m):
        s, t = [int(v) for v in input().split()]
        g[s].append(t)

    tsort(n, g)

Submission status: Runtime Error

Solution code:

# -*- coding: utf-8 -*-
# 文字列の入力
import math

V,E = map(int ,input().split())
X = []

for i in range(E):
	s_i, t_i = map(int , input().split())
	if(s_i in X):
		if(t_i in X):
			t = X.index(t_i)
			s = X.index(s_i)
			if(s > t):
				X.remove(t_i)
				X.insert(s,t_i)
		else:
			X.append(t_i)
	else:
		if(t_i in X):
			t = X.index(t_i)
			X.insert(t, s_i)
		else:
			X.append(s_i)
			X.append(t_i)
for i in range(V):
	print(X[i])

Submission status: Runtime Error

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

Submission status: Runtime Error

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]*E
yet = [True]*E
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(E):
    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: Runtime Error

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(E)]
indeg = [0]*E
yet = [True]*E
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(E):
    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: Runtime Error

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())
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: Runtime Error

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 and color[j]==0 :
                indeg[j]-=1
                if indeg[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
start=[]
ans=deque()
q=deque()
for i in xrange(v):
    s,t=map(int,raw_input().split())
    m[s][t]=t
    indeg[t]+=1
Topologicalsort()
for i in ans:
    print(i)

Submission status: Runtime Error

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

Submission status: Runtime Error

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)

for v in out:
    print(v)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
V, E = map(int, stdin.readline().split())
adj_list = [[] for _ in [] * V]
is_visited = [False] * V
for _ in [] * 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')