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:
#!/usr/bin/env python3

"""
Performs topological sorting of the given DAG using Kahn's algorithm.

Verification: []()
"""

import heapq


class TopologicalSortError(Exception):
    """This exception is raised when something gets wrong while performing `topological_sort`.
    """    
    pass


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.

    Parameters:

    - `num_vs`: The number of vertices of the DAG.
    - `adj_vs` The adjacency list of the DAG.

    Returns: the lexicographically least topological order as a list.
    
    Raises `TopologicalSortError` if the given graph is not a DAG.
    """
    
    in_deg = [0 for _ in range(num_vs)]
    for dests in adj_vs:
        for dest in dests:
            in_deg[dest] += 1
    sorted_vs = []
    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:
V,E = list(map(int,input().split()))

#訪問済の頂点を保持
visit=[]
no_visit=list(range(V))

#各頂点の入次数
enter=[0]*V

#隣接リスト
ad_list=[[] for _ in range(V)]

for e in range(E):
    start,end=list(map(int,input().split()))
    ad_list[start].append(end)
    enter[end]+=1
    
enter , ad_list

while True:
    if len(visit)==V:
        break
        
    for n_v_idx,n_v in enumerate(no_visit):
        e=enter[n_v]
        if e == 0:
            v=no_visit.pop(n_v_idx)
            visit.append(v)
            for a in ad_list[n_v]:
                enter[a]=enter[a]-1
for v in visit:
    print(v)

Submission status: Accepted

Solution code:
from collections import deque

class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)
            self.rev[e[1] - indexed].append(e[0] - indexed)
            self.deg[e[1] - indexed] += 1

    def topological_sort(self):
        deg = self.deg[:]
        res = [i for i in range(self.n) if deg[i] == 0]
        queue = deque(res)
        used = [False for _ in range(self.n)]
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                deg[adj] -= 1
                if deg[adj] == 0:
                    queue.append(adj)
                    res.append(adj)
        return res


import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, E, 0)
print('\n'.join(map(str, g.topological_sort())))

Submission status: Accepted

Solution code:
from collections import deque

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

#グラフを格納
g = [[] for _ in range(V)]

#点に入ってくる矢印の数を記録
in_E = [0 for _ in range(V)]

for _ in range(E):
    s, t = map(int, input().split())
    g[s].append(t)
    in_E[t] += 1

# print(in_E)

d = deque()
#in_Eが0をdequeに格納
for i in range(V):
    if in_E[i] == 0:
        d.append(i)

ans = []

while d:
    # print("d", d)
    v = d.popleft()
    # print("v", v)
    # print("in_E", in_E)
    for u in g[v]:
        # print("u", u)
        in_E[u] -= 1
        if in_E[u] == 0:
            d.append(u)
    ans.append(v)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque
ans = deque()
V,E = map(int,input().split())
C = [[] for _ in range(V)]
for _ in range(E):
    tmp = list(map(int,input().split()))
    C[tmp[0]].append(tmp[1])

visited = [False]*V


def DFS(node):
    visited[node] = True
    for adj in C[node]:
        if not visited[adj]:
            DFS(adj)
    ans.appendleft(node)


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


for node in ans:
    print(node)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	topological_sort
# CreatedDate:  2020-05-18 14:33:31 +0900
# LastModified: 2020-05-18 14:50:54 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    v,e = map(int,input().split())
    path_list = [[] for _ in range(v)]
    to_there = [0]*v
    for _ in range(e):
        s,t = map(int,input().split())
        path_list[s].append(t)
        to_there[t]+=1

    stack_list = [i for i,x in enumerate(to_there) if x==0]
#    print(to_there)
    while stack_list:
        u = stack_list.pop()
        for v in path_list[u]:
            to_there[v]-=1
            if to_there[v]==0:
                stack_list.append(v)
        print(u)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
deg = [0]*N
for _ in [0]*M:
    a, b = map(int, input().split())
    G[a].append(b)
    deg[b] += 1

q = deque()

for v, d in enumerate(deg):
    if d == 0:
        print(v)
        q.append(v)

while q:
    v = q.popleft()
    for u in G[v]:
        deg[u] -= 1
        if deg[u] == 0:
            print(u)
            q.append(u)

Submission status: Accepted

Solution code:
import queue

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

G = [[] for _ in range(V)]
visited = [False] * V
indeg = [0] * V
out = []

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

for i in range(V):
    for j in range(len(G[i])):
        indeg[G[i][j]] += 1

q = queue.Queue()
for i in range(V):
    if indeg[i] == 0 and not visited[i]:
        q.put(i)
        visited[i] = True
        while not q.empty():
            u = q.get()
            out.append(u)
            for j in range(len(G[u])):
                v = G[u][j]
                indeg[v] -= 1
                if indeg[v] == 0 and not visited[v]:
                    visited[v] = True
                    q.put(v)

for el in out:
    print(el)

Submission status: Accepted

Solution code:
import sys,collections
V,E = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
#sdw = [[src1 dist1 d1][src1 dist1 d1]...]# vect source1 -> distance1 distances
INF = float("inf")

st = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param

G = [[] for _ in range(V)]

for s,t in st:
    G[s].append(t)

visited = set()
indeg = [0]*V
ret = []
def bfs(s):
    q = collections.deque([s])
    visited.add(s)
    while q:
        u = q.popleft()
        ret.append(u)
        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and not v in visited:
                visited.add(v)
                q.append(v)

def topologicalSort_bfs():
    for a in G:
        for t in a:
            indeg[t] += 1
    #print(G,indeg)
    for i in range(V):
        if indeg[i] == 0 and not i in visited:
            bfs(i)

def dfs(s):
    #print("s:",s)
    if s in visited:
        return
    for e in G[s]:
        dfs(e)
    ret.append(s)
    visited.add(s)

def topologicalSort_dfs():
    for i in range(V):
        dfs(i)
    ret.reverse()

topologicalSort_bfs()
#topologicalSort_dfs()
print(*ret,sep='\n')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    V, E = MI()
    edges = []

    for i in range(E):
        edges.append(tuple(MI()))

    in_cnt = defaultdict(int)
    outs = defaultdict(list)
    for a, b in edges:
        in_cnt[b] += 1
        outs[a].append(b)

    res = []
    queue = deque([i for i in range(V) if in_cnt[i] == 0])
    while len(queue) != 0:
        v = queue.popleft()
        res.append(v)
        for nxt_v in outs[v]:
            in_cnt[nxt_v] -= 1
            if in_cnt[nxt_v] == 0:
                queue.append(nxt_v)

    for i in range(V):
        print(res[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
res = []
def recursion(v, E, state) -> bool:
    # base case
    if state[v]:
        return state[v] == 1
    # recursion
    state[v] = -1
    flag = all(recursion(nv, E, state) for nv in E[v])
    if flag:
        state[v] = 1
        res.append(v)
    return flag

def resolve():
    n, m = map(int,input().split())
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int,input().split())
        E[u].append(v)
    state = [0] * n # 0 : unvisited, -1 : visited & uncalculated, 1 : calculated
    for v in range(n):
        recursion(v, E, state)
    print(*res[::-1], sep = '\n')
resolve()

Submission status: Accepted

Solution code:
from collections import deque
N,E=map(int,input().split())
G=[[] for i in range(N)]
In=[0]*N
for i in range(E):
    s,t=map(int,input().split())
    G[s].append(t)
    In[t]+=1
S=deque([i for i in range(N) if In[i]==0])
res=[]
while S:
    b=S.popleft()
    for nv in G[b]:
        In[nv]-=1
        if(In[nv]==0):
            S.append(nv)
    res.append(b)
print(*res,sep='\n')

Submission status: Accepted

Solution code:
from collections import deque

V, E = list(map(int, input().split()))
edge = [[] for i in range(V)]
in_num = [0] * V

for i in range(E):
    s, t = list(map(int, input().split()))
    edge[s].append(t)
    in_num[t] += 1
    
q = deque()

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

ans = deque()

while q:
    v = q.popleft()
    
    ans.append(v)
    
    for u in edge[v]:
        in_num[u] -= 1
        if in_num[u] == 0: q.append(u)
        
for a in ans: print(a)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
G = [[] for i in range(n)]
deg = [0 for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    G[b].append(a)
    deg[a] += 1

from collections import deque
q = deque()
add,pop=q.append,q.popleft
for i in range(n):
    if deg[i]==0:
        add(i)

order = []
while q:
    v = pop()
    order.append(v)
    for nv in G[v]:
        deg[nv] -= 1
        if deg[nv] == 0:
            add(nv)

for i in order[::-1]:
    print(i)

Submission status: Accepted

Solution code:
#https://qiita.com/drken/items/996d80bcae64649a6580 3-3. 二部グラフ判定
from collections import deque

# 頂点数と辺数
N, M = map(int, input().split())

# グラフ入力受取
G = [[] for _ in range(N)]
deg = [0]*N # 各頂点の出次数
for i in range(M):
    a, b = map(int, input().split())
    G[b].append(a) # 逆向きに辺を張る
    deg[a]+=1 # 出次数

# シンクたちをキューに挿入する
que = deque()
for i in range(N):
    if deg[i] == 0:
        que.append(i)

# 探索開始
order = []
while len(que)!=0:
    # キューから頂点を取り出す
    v = que.popleft()
    order.append(v)

    # v へと伸びている頂点たちを探索する
    for nv in G[v]:
        # 辺 (nv, v) を削除する
        deg[nv]-=1

        # それによって nv が新たにシンクになったらキューに挿入
        if deg[nv] == 0:
            que.append(nv)

# 答えをひっくり返す
order.reverse()
for i in order:
    print(i)

Submission status: Accepted

Solution code:
def zadanie_2():

    # n - liczba wierzchołków, m - liczba łuków
    [n, m] = list(map(int, input().strip().split(" ")))

    sasiedzi = [[] for _ in range(n)]
    stopnie = [0 for _ in range(n)]
    kolejka = []
    kolejnosc = []

    for i in range(m):
        luk = list(map(int, input().strip().split(" ")))
        sasiedzi[luk[0]].append(luk[1])
        stopnie[luk[1]] += 1

    for i in range(n):
        if stopnie[i] == 0:
            kolejka.append(i)

    while len(kolejka) > 0:
        wierzcholek = kolejka.pop(0)
        kolejnosc.append(wierzcholek)
        for sasiad in sasiedzi[wierzcholek]:
            stopnie[sasiad] -= 1
            if stopnie[sasiad] == 0:
                kolejka.append(sasiad)

    for i in range(len(kolejnosc)):
        print(str(kolejnosc[i]), end="")
        if i < len(kolejnosc) - 1:
            print("")


zadanie_2()

Submission status: Accepted

Solution code:
from collections import deque

v, e = map(int,input().split())
edges = [[] for _ in range(v)]
in_num = [0 for _ in range(v)]

for _ in range(e):
    s,t = map(int, input().split())
    edges[s].append(t)
    in_num[t] += 1

q = deque()

for i in range(len(in_num)):
    if in_num[i] == 0:
        q.append(i)

ans = []
while q:
    node = q.popleft()
    ans.append(node)
    for v in edges[node]:
        in_num[v] -= 1
        if in_num[v] == 0:
            q.append(v)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque


def topologicalSort(v,e):
    global color,out,indeg
    color=["white" for _ in range(v)]
    indeg=[[0,[]] for _ in range(v)]
    out=[]

    for i in range(e):
        s,t=map(int,input().split())
        indeg[s][0] +=1
        indeg[t][1] +=[s]

    for i in range(v):
        if indeg[i][0]==0 and color[i]=="white":
            BFS(i)

    return out[::-1]


def BFS(s):
    Q=deque([])
    Q.append(s)
    color[s]="gray"
    while len(Q)!=0:
        u=Q.popleft()
        out.append(u)

        for i in indeg[u][1]:
            indeg[i][0] -=1
            if indeg[i][0]==0 and color[i]=="white":
                color[i]="gray"
                Q.append(i)


v,e=map(int,input().split())
for i in topologicalSort(v,e):
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

v, n = map(int, input().split())
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:
from collections import deque
from collections import defaultdict
V, E = map(int, input().split())
d = [0]*V
G = defaultdict(list)
for i in range(E):
    s, t = map(int, input().split())
    d[t] += 1
    G[s].append(t)
q = deque([])
for i in range(V):
    if d[i] == 0:
        q.append(i)
ans = []
while q:
    s = q.popleft()
    ans.append(s)
    for t in G[s]:
        d[t] -= 1
        if d[t] == 0:
            q.append(t)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def topologicalSort():
    input = sys.stdin.readline
    V, E = map(int, input().split())
    Parent_node = [0 for _ in range(V)]
    Son_node = [set() for _ in range(V)]
    for _ in range(E):
        a, b = map(int, input().split()) #default: 0-indexed
        Son_node[a] |= {b}
        Parent_node[b] += 1

    stack = deque() #入次数が0のノードを格納する
    for i, p in enumerate(Parent_node):
        if p == 0: stack.append(i)

    sortedArray = []
    while stack:
        nowNode = stack.popleft()
        sortedArray.append(nowNode)
        for nextNode in Son_node[nowNode]:
            Parent_node[nextNode] -= 1
            if Parent_node[nextNode] == 0: stack.append(nextNode)

    for a in sortedArray: print(a)

    return len(sortedArray) == V

if __name__ == "__main__":
    topologicalSort()

Submission status: Accepted

Solution code:
from collections import deque


def topological_sort(indeg, tonodes, v):
    nodes = deque([])
    visited = deque([])
    for i in range(v):
        if indeg[i] == 0:
            nodes.append(i)
    while len(nodes) > 0:
        i = nodes.popleft()
        visited.append(i)
        for j in tonodes[i]:
            indeg[j] -= 1
            if indeg[j] == 0:
                nodes.append(j)
    return visited


def main():
    ve = input().split()
    v, e = tuple(map(int, ve))
    indeg = [0 for _ in range(v)]
    tonodes = [[] for _ in range(v)]

    for _ in range(e):
        st = input().split()
        s, t = tuple(map(int, st))
        indeg[t] += 1
        tonodes[s].append(t)
    visited = topological_sort(indeg, tonodes, v)
    while len(visited) > 0:
        print(visited.popleft())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

dic = {}
pnum = [0] * V

for i in range(E):

    s,t = map(int,input().split())

    pnum[t] += 1
    
    if s not in dic:
        dic[s] = []
    dic[s].append(t)

q = deque([])
ans = []

for i in range(V):

    if pnum[i] == 0:
        q.append(i)
        ans.append(i)

while len(q) > 0:

    now = q.popleft()

    if now not in dic:
        continue

    for i in dic[now]:
        pnum[i] -= 1

        if pnum[i] == 0:
            q.append(i)
            ans.append(i)

for i in range(V):
    print (ans[i])

Submission status: Accepted

Solution code:
def topologicalSort(g: list, deg: list):
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				ret.append(nxt)
				q.append(nxt)
	return ret

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s].append(t)
		deg[t] += 1
	print("\n".join(map(str, topologicalSort(g, deg))))

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

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

adjacents = []

for i in range(V):
  adjacents.append([])

for i in range(E):
  s, t = map(int, input().split())
  adjacents[t].append(s)

def topological_sort(num, adjacents):
  colors = ["white"] * num
  result = []

  def dfs(u):
    if colors[u] == "black":
      return

    colors[u] = "black"

    for a in adjacents[u]:
      if colors[a] != "black":
        dfs(a)

    result.append(u)

  for n in range(num):
    dfs(n)

  return result

for i in topological_sort(V, adjacents):
  print(i)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import queue

WHITE = 0
GRAY = 1
BLACK= 2

def topologicalSort(s):
    Q.put(s)
    color[s] = GRAY
    while not Q.empty():
        u = Q.get()
        out.append(u)
        
        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and color[v] == WHITE:
                color[v] = GRAY
                Q.put(v)
            



nums=list(map(int,input().split()))
n = nums[0]
e = nums[1]

color = [WHITE] * n
G = [[] for i in range(n)]
indeg = [0] * n

for i in range(e):
    nums=list(map(int,input().split()))
    G[nums[0]].append(nums[1])
    indeg[nums[1]] += 1

Q = queue.Queue()
out = []

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

for i in range(n):
    print(out[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

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

def Topological_Sort(G):
    # DAGの隣接リストを受け取って、トポロジカルソートしたリストを返す
    V=len(G)
    div=[0]*V
    for gi in G:
        for ei  in gi:
            div[ei]+=1
    used=[0]*V
    result=[]

    def bfs(node):
        que = collections.deque([node])
        used[node] = 1
        while que:
            tmp = que.popleft()
            result.append(tmp)
            for v in G[tmp]:
                div[v] -= 1
                if div[v] == 0 and not used[v]:
                    que.append(v)
                    used[v] = 1

    for i in range(V):
        if div[i]==0 and not used[i]:
            bfs(i)
    return result

    
ans=Topological_Sort(G)
print(*ans,sep="\n")

# def bfs(node):
#     que=collections.deque([node])
#     used[node]=1
#     while que:
#         tmp=que.popleft()
#         ans.append(tmp)
#         for v in G[tmp]:
#             div[v]-=1
#             if div[v]==0 and not used[v]:
#                 que.append(v)
#                 used[v]=1
    



# for i in range(V):
#     if div[i]==0 and not used[i]:
#         bfs(i)

# for a in ans:
    # print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
INF = 10**30
sys.setrecursionlimit(10000000)
from collections import deque
G = []
into = [] # 入次数


def topological_sort(n):
    global into
    ans = []
    unvisited = [True] * n
    for i in range(n):
        if into[i] == 0 and unvisited[i]:
            q = deque()
            q.append(i)
            while len(q) > 0:
                node = q.popleft()
                ans.append(node)
                unvisited[node] = False
                for v in G[node]:
                    into[v] -= 1
                    if into[v] == 0:
                        q.append(v)
    return ans

visited = []
answer = deque()
def rec(v):
    global visited
    visited[v] = True

    for node in G[v]:
        if not visited[node]:
            rec(node)
    answer.appendleft(v)

def dfs_topolo(n):
    for i in range(n):
        if not visited[i]:
            rec(i)

def main():
    global G, into, visited
    v, e = list(map(int, input().strip().split()))
    G = [[] for _ in range(v)]
    visited = [False] * v
    into = [0] * v
    for i in range(e):
        s, t = list(map(int, input().strip().split()))
        G[s].append(t)
        into[t] += 1
    # ans = topological_sort(v)
    # for p in ans:
    #     print(p)
    dfs_topolo(v)
    for p in answer:
        print(p)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

v,e = map(int,input().split())
L = []
ins = [0]*v
DAG = [[] for i in range(v)]
ans = []
for i in range(e):
    a,b = map(int,input().split())
    DAG[a].append(b)
    ins[b] += 1
start = 0
S = deque([])
for i in range(v):
    if ins[i] == 0:
        S.append(i)
while len(S) > 0:
    cur = S.popleft()
    ans.append(cur)
    for e in DAG[cur]:
        ins[e] -= 1
        if ins[e] == 0:
            S.append(e)
for i in range(v):
  print(ans[i])

Submission status: Accepted

Solution code:
Vnum = 0
Enum = 0
Edge = {}
L = []
V = []

def visit(n):
    if V[n] == 1:
        sys.exit()
    elif V[n] == 0:
        V[n] = 1
        if n in Edge.keys():
            for m in Edge[n]:
                visit(m)
        V[n] = 2
        L.append(n)
        return True

Vnum,Enum = map(int,input().split())
V = [ 0 for v in range(Vnum) ]
for _ in range(Enum):
    s,t = map(int,input().split())
    if s in Edge.keys():
        Edge[s].append(t)
    else:
        Edge[s] = [t]
#print(Edge)

for n in range(Vnum):
    if V[n] == 0:
        visit(n)
#print(V)
L.reverse()
for a in L:
    print(a)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    sys.setrecursionlimit(100000)
    V, E = read_ints()
    G = [set() for _ in range(V)]
    for _ in range(E):
        s, t = read_ints()
        G[s].add(t)
    print(*solve(V, E, G), sep='\n')


def solve(V, E, G):
    topo = []
    done = [False] * V

    def dfs(i):
        if done[i]:
            return
        for j in G[i]:
            dfs(j)
        done[i] = True
        topo.append(i)

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

    topo.reverse()
    return topo


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from typing import List, Tuple

def topological_sort(n: int, m: int, G: List[List[int]]) -> List[int]:
	for u in range(n):
		if color[u] == "WHITE":
			dfs(u)
	return L[::-1]

def dfs(u: int) -> None:
	if color[u] == "GRAY":
		print("Graph is not DAG")
		exit()
	if color[u] == "BLACK":
		return
	color[u] = "GRAY"
	for v in G[u]:
		dfs(v)
	color[u] = "BLACK"
	L.append(u)


if __name__ == "__main__":
	n, m = map(int, input().split())
	G = [[] for _ in range(n)]
	color: List[str] = ["WHITE" for _ in range(n)]
	L: List[int] = []
	for _ in range(m):
		s, t = map(int, input().split())
		G[s].append(t)
	L = topological_sort(n, m, G)
	for v in L:
		print(v)

Submission status: Accepted

Solution code:
# GRL_4_B: Topological Sort
import sys


# input
v, e = map(int, sys.stdin.readline().strip().split())
G = [[] for _ in range(v)]
indeg = [0] * v
for i in range(e):
    s, t = map(int, sys.stdin.readline().strip().split())
    G[s].append(t)
    indeg[t] += 1
# print('G : {}\nindeg : {}'.format(G, indeg))

# calc
ans = []


def dfs(u):
    if indeg[u] == 0:
        ans.append(u)
        for i in G[u]:
            indeg[i] -= 1
            dfs(i)


indeg_start = indeg.copy()
for i in range(v):
    if indeg_start[i] == 0:  # 入ってくる辺がない = 最初のノードからスタート
        dfs(i)

# print(indeg)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:

def topological_sort(nodes, edges) -> []:
    visited = set()
    result = []

    def dfs(v):
        if v not in visited:
            visited.add(v)
            for u in edges[v]:
                dfs(u)
            result.append(v)

    for s in nodes:
        dfs(s)

    return result

def aoj_system_test():
    """
    The problem of aoj for topological sort use special judge.
    So, I can't verify using online-judge-tools. (T T)
    """
    V, E = map(int, input().split())
    nodes = []
    edges = []
    for i in range(V):
        nodes.append(i)
        edges.append([])
    for _ in range(E):
        a, b = map(int, input().split())
        edges[b].append(a)
    ret = topological_sort(nodes, edges)
    for v in ret:
        print(v)

if __name__ == '__main__':
    aoj_system_test()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

#入力⇒V：頂点の数、E：辺の数
V,E = map(int,input().split())
#入力⇒s：開始点、e：終了点
se_list = [list(map(int,input().split())) for _ in range(E)]

#定義⇒{s1:[end1,end2,...],s2:[],...}
s_dic = {}

#定義⇒[頂点0に入ってくる矢印の数,頂点1に入ってくる矢印の数,.....]
e_list = [0 for _ in range(V)]

#s_dic,e_listを作成
for s,e in se_list:
    if s in s_dic:
        s_dic[s].append(e)
    else:
        s_dic[s] = [e]
    e_list[e] += 1

#キューの初期化（入ってくる矢印が0のものをキューに追加）
dfs_q = deque()
for v in range(V):
    if e_list[v] == 0:
        dfs_q.append(v)

#トポロジカルソートされた配列（今回の答え）
topological_sort = []

#キューがなくなるまで実行
while dfs_q:
    v_from = dfs_q.pop()
    topological_sort.append(v_from)
    if v_from in s_dic:
        for v_to in s_dic[v_from]:
            e_list[v_to] -= 1
            if e_list[v_to] == 0:
                dfs_q.append(v_to)

#答えの出力
for v in topological_sort:
    print(v)

Submission status: Accepted

Solution code:
from collections import deque
v, e  = map(int, input().split())

Edg = [[] for _ in range(v)]
inDeg = [0 for _ in range(v)]
Done = [0 for _ in range(v)]
for _ in range(e):
    s,t = map(int, input().split( ))
    Edg[s].append(t)
    inDeg[t] += 1

Q= deque()

ans = []
for u in range(v):
    if not inDeg[u]:
        Q.append(u)

while Q:
    u = Q.popleft()
    ans.append(u)
    for t in Edg[u]:
        inDeg[t] -= 1
        if inDeg[t] == 0 and not Done[t]:
            Q.append(t)
            Done[t] = 1

    
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
  q = deque()
  q.append(s)
  while len(q) > 0:
    u = q.popleft()
    searched[u] = True
    res.append(u)
    for v in adj[u]:
      indeg[v] -= 1
      if indeg[v] == 0 and not searched[v]:
        q.append(v)

V, E = map(int, input().split())
adj = [[] for i in range(V)]
indeg = [0 for i in range(V)]

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

searched = [False for i in range(V)]
res = []

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

for u in res:
  print(u)