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:
nv, ne = map(int, input().split(' '))
in_degs = [0] * nv
q = []
outs = {}
o = []

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

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

    in_degs[t] += 1

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

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

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

[print(v) for v in o]

Submission status: Accepted

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

import sys
import os
import pprint
from queue import Queue

"""Topological Sort"""

#fd = os.open('GRL_4_B_5.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(E):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    indig[t] += 1

q = Queue()
out = []

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

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

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

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

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

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

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

Submission status: Accepted

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

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

    for v in ordering:
        print(v)


main()

Submission status: Accepted

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

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

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


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


main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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


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

    ordering.append(u)


main()

Submission status: Accepted

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(m):
  s, t = [int(i) for i in input().strip().split(' ')]
  G[s].add(t)
  revG[t].add(s)


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

Submission status: Accepted

Solution code:
#??±???????????¢?´¢
import collections

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

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

Out = collections.deque()


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

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

Submission status: Accepted

Solution code:
import collections

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

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

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

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
def topological_sort(G):
  d = {}
  nodes = set()
  for i in G:
    if i not in d:
      d[i] = set()
    for j in G[i]:
      if j not in d:
        d[j] = set()
      d[j].add(i)
  for i in d:
    if len(d[i]) == 0:
      nodes.add(i)
  visited = set()
  ret = []
  while len(visited) < len(G):
    n = nodes.pop()
    if n not in visited:
      for j in G[n]:
        d[j].discard(n)
        if len(d[j]) == 0 and j not in visited:
          nodes.add(j)
      ret.append(n)
      visited.add(n)
  return ret




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

L = topological_sort(G)

for n in L:
  print(n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=jp

"""
import sys
from collections import deque


def bfs(u, result, out_edge, in_degree, processed):
    q = deque()
    q.append(u)
    processed[u] = True
    while q:
        u = q.popleft()
        result.append(u)
        for e in out_edge[u]:
            in_degree[e] -= 1
            if in_degree[e] == 0 and processed[e] == False:
                processed[e] = True
                q.append(e)





def solve(V, in_degree, out_edge):
    result = []
    processed = [False for _ in range(V)]

    for i, u in enumerate(in_degree):
        if u == 0 and processed[i] == False:
            bfs(i, result, out_edge, in_degree, processed)
    return result


def main(args):
    V, E = [int(x) for x in input().split(' ')]
    in_degree = [0 for _ in range(V)]
    out_edge = [[] for _ in range(V)]
    for _ in range(E):
        s, t = [int(x) for x in input().split(' ')]
        out_edge[s].append(t)
        in_degree[t] += 1

    result = solve(V, in_degree, out_edge)
    print('\n'.join(map(str, result)))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from collections import defaultdict


def dfs(u, used, edges, result):
    used[u] = True
    for v in edges[u]:
        if not used[v]:
            dfs(v, used, edges, result)
    result.append(u)


def main():
    N, M = map(int, input().split())

    used = [False] * N
    edges = defaultdict(list)
    for _ in range(M):
        s, t = map(int, input().split())
        edges[s].append(t)

    result = []
    for i in range(N):
        if not used[i]:
            dfs(i, used, edges, result)

    print(*result[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def topological_sort(N, edges):
    def dfs(u):
        used[u] = True
        for v in edges[u]:
            if not used[v]:
                dfs(v)
        result.append(u)

    used = [False] * N
    result = []
    for i in range(N):
        if not used[i]:
            dfs(i)

    return result[::-1]


def main():
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for _ in range(M):
        s, t = map(int, input().split())
        edges[s].append(t)

    ans = topological_sort(N, edges)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

def inpl(): return tuple(map(int, input().split()))

V, E = inpl()
indeg = [0] * V
adj = {k: [] for k in range(V)}

for _ in range(E):
    s, t = inpl()
    adj[s].append(t)
    indeg[t] += 1

Q = deque([i for i, ind in enumerate(indeg) if ind == 0])
res = []

while Q:
    q = Q.popleft()
    for i in adj[q]:
        indeg[i] -= 1
        if indeg[i] == 0:
            Q.append(i)
    res.append(q)

for r in res:
    print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

V, E = map(int, input().split())
G = defaultdict(list)

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

ans = deque([])
visited = defaultdict(bool)
def visit(v):
    if visited[v]: return
    visited[v] = True
    for k in G[v]:
        visit(k)
    ans.appendleft(v)

for v in range(V):
    visit(v)

print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict
vertice, edge = (int(n) for n in input().split(" "))
connect = defaultdict(list)
indegree = [0 for n in range(vertice)]
for _ in range(edge):
    s, t = (int(n) for n in input().split(" "))
    connect[s].append(t)
    indegree[t] += 1
answer = []
zeroin = []
for i, n in enumerate(indegree):
    if n == 0:
        zeroin.append(i)
while len(zeroin) > 0:
    next_v = zeroin.pop()
    indegree[next_v] -= 1
    answer.append(next_v)
    for c in connect[next_v]:
        indegree[c] -= 1
        if indegree[c] == 0:
            zeroin.append(c)
for a in answer:
    print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
re = sys.stdin
vertice, edge = (int(n) for n in re.readline().split(" "))
connect = defaultdict(list)
indegree = [0 for n in range(vertice)]
for _ in range(edge):
    s, t = (int(n) for n in re.readline().split(" "))
    connect[s].append(t)
    indegree[t] += 1
answer = []
zeroin = []
for i, n in enumerate(indegree):
    if n == 0:
        zeroin.append(i)
while len(zeroin) > 0:
    next_v = zeroin.pop()
    indegree[next_v] -= 1
    answer.append(next_v)
    for c in connect[next_v]:
        indegree[c] -= 1
        if indegree[c] == 0:
            zeroin.append(c)
for a in answer:
    print(a)

Submission status: Accepted

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

from collections import deque


if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    E = [set() for _ in range(n)]
    for _ in range(m):
        s, t = [int(s) for s in input().split(" ")]
        E[s].add(t)

    color = [0] * n
    indeg = [0] * n
    for s in range(n):
        for t in E[s]:
            indeg[t] += 1

    Q = deque()
    out = []

    def bfs(s):
        Q.append(s)
        color[s] = 1
        while Q:
            u = Q.popleft()
            out.append(u)
            for v in E[u]:
                indeg[v] -= 1
                if indeg[v] == 0 and color[v] == 0:
                    color[v] = 1
                    Q.append(v)

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

    print("\n".join(map(str, out)))

Submission status: Accepted

Solution code:
V, E = map(int,input().split())

L = []
visited = [0 for i in range(V)]
edges = [[] for i in range(V)]
flag = 0

def visit(x):
  if visited[x] == 1:
    flag = 1
  elif not visited[x]:
    visited[x] = 1
    for e in edges[x]:
      visit(e)
    visited[x] = 2
    L.insert(0,x)

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

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

for i in L:
  print(i)

Submission status: Accepted

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]:
        if e not in V:
            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()

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

Submission status: Accepted

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]:
        if e not in V:
            dfs(e)
    ans.append(n)
    V.add(n)


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

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

Submission status: Accepted

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)


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


print(*topological_sort(G), sep="\n")

Submission status: Accepted

Solution code:
from collections import deque


def topological(N, LIST):  # トポロジカルソート:DAGに適用可
    incnt = [0] * N
    CHILD = [set() for _ in range(N)]
    for a, b in LIST:
        CHILD[a].add(b)
        incnt[b] += 1

    TPLGSORT = []
    que = deque([i for i, num in enumerate(incnt) if num == 0])
    while len(que) > 0:
        q = que.popleft()
        for i in CHILD[q]:
            incnt[i] -= 1
            if incnt[i] == 0:
                que.append(i)
        TPLGSORT.append(q)
    return TPLGSORT


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

tplg = topological(n, ab)
print(*tplg, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
# sts -> start topological sort   
def sts():
    for i in g:
        for j in i:
            incnt[j]+=1 
    for i in range(v):
        if incnt[i]==0:
            q.append(i)
    # Now start deleting elements
    while q:
        e=q.popleft()
        ans.append(e)
        for i in g[e]:
            incnt[i]-=1
            if incnt[i]==0:
                q.append(i)
    for i in ans:
        print(i)
            
v,e=map(int,input().split())
g=[[] for i in range(v)]
# incnt -> no of indirected edges to a vertex
incnt=[0]*v
# q -> queue containing nodes with 0 indirected edges
q=deque()
# ans -> topological sorted array
ans=[]
for i in range(e):
    x,y=map(int,input().split())
    g[x].append(y)
sts()

Submission status: Accepted

Solution code:
from collections import deque

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

def topological_sort(adj, inflow):
    is_visited = [False] * len(inflow)
    res = []

    def bfs(s):
        #sを始点とする
        q = deque([s])
        is_visited[s] = True
        res.append(s)
        while q:
            p = q.popleft()
          
            for r in adj[p]:
                inflow[r] -= 1
                if (inflow[r] == 0) and (not is_visited[r]):
                    q.append(r)
                    is_visited[r] = True
                    res.append(r)

    for x in range(len(inflow)):
        if (inflow[x] == 0) and (not is_visited[x]):
            bfs(x)
    return res

for i in topological_sort(adj, inflow):
    print(i)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    deg = [0]*N
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        G[a].append(b)
        deg[b] += 1

    from collections import deque

    def topological_sort():
        que = deque()
        ans = []*N
        for i in range(N):
            if deg[i] == 0:
                que.append(i)
                ans.append(i)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

from collections import deque, defaultdict

def bfs(s):
    Q.append(s)
    color[s] = 1

    while Q:
        u = Q.popleft()

        out.append(u)

        for edge in range(e):
            s, t = list(map(int, lines[edge+1].split()))
            if s == u:
                indeg[t] -= 1
                if indeg[t] == 0 and color ==0:
                    color[t] = 1
                    Q.append(t)


lines = stdin.readlines()

v, e = list(map(int, lines[0].split()))

out = []
outs = defaultdict(list)


color = [0] * v
indeg = [0] * v

for i in range(e):
    s, t = list(map(int, lines[i+1].split()))
    outs[s].append(t)
    indeg[t] += 1

Q = deque(v1 for v1 in range(v) if indeg[v1] == 0)

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

    for v2 in outs[v1]:
        indeg[v2] -= 1
        if indeg[v2] == 0:
            Q.append(v2)

for i in out:
    print(i)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

V, E = MAP()
st = [LIST() for _ in range(E)]

graph = [[] for _ in range(V)]
dag = [0]*V
for s, t in st:
	graph[s].append(t)
	dag[t] += 1

ans = [i for i, x in enumerate(dag) if x == 0]
q = deque([i for i, x in enumerate(dag) if x == 0])
while q:
	S = q.popleft()
	for node in graph[S]:
		dag[node] -= 1
		if dag[node] == 0:
			ans.append(node)
			q.append(node)

if sum(dag):
	print(-1)
else:
	print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)

V, E = map(int, input().split())
G = [[] for _ in range(V)]

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

visited = [0]*V
ans = deque([])

def dfs(u):
    visited[u] = 1
    for i in G[u]:
        if visited[i] == 0:
                dfs(i)
    ans.appendleft(u)

for s in range(V):
    if visited[s] == 0:
        dfs(s)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import queue

def bfs(u):
    q = queue.Queue()
    q.put(u)
    
    while not q.empty():
        v = q.get()
        color[v] = 'black'
        ans.append(v)
        for w in Adj[v]:
            indeg[w] -= 1
            if indeg[w] == 0 and color[w] == 'white':
                q.put(w)
                
    return
        

n,m = map(int,input().split())
color = ['white' for _ in range(n)]
Adj = [[] for _ in range(n)]
indeg = [0]*n
ans = []
for i in range(m):
    s,t = map(int,input().split())
    Adj[s].append(t)
    indeg[t] += 1
    
for i in range(n):
    if indeg[i] == 0 and color[i] == 'white':
        bfs(i)
        
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
from typing import List, Optional


def topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Optional[List[int]]:
    """Topological sort that uses Kahn's algorithm and is able to detect cycles.
    Returns:
        If the given graph is DAG, a list of sorted vertices is returned.
        Otherwise, if loops are detected, None is returned.
    """
    V = len(graph) + first_index
    order = [i for i in range(first_index, V) if not in_degrees[i]]
    queue = deque(order)

    while queue:
        u = queue.popleft()
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                queue.append(v), order.append(v)

    return order if len(order) + first_index == V else None


def grl_4_b():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_B
    V, _, *ST = map(int, open(0).read().split())
    graph = [[] for _ in range(V)]
    in_degrees = [0] * V
    for s, t in zip(*[iter(ST)] * 2):
        graph[s].append(t)
        in_degrees[t] += 1

    res = topological_sort(graph, in_degrees)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    grl_4_b()

Submission status: Accepted

Solution code:
from collections import deque
def topological_sort(n,G):
    seq_sorted = []
    st = deque()

    ct_to_edges = [0]*n
    for edges in G:
        for node in edges:
            ct_to_edges[node]+=1
    
    for i,ct in enumerate(ct_to_edges):
        if ct==0:
            st.append(i)
    
    while st:
        node = st.pop()
        seq_sorted.append(node)
        for node in G[node]:
            ct_to_edges[node]-=1
            if ct_to_edges[node]==0:
                st.append(node)
    
    return seq_sorted
def main():
    n,m = map(int,input().split())
    G = [[] for _ in range(n)]
    for _ in range(m):
        s,t = map(int,input().split())
        G[s].append(t)

    topo_seq =  topological_sort(n,G)
    for i in topo_seq:
        print(i)
main()

Submission status: Accepted

Solution code:
v,e=map(int,input().split())
from collections import defaultdict
incnt=defaultdict(int)
edges=[[] for i in range(0+v)]
for i in range(e):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    incnt[__]+=1
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    incnt[__]+=1
    """
"""#weighted->erase
from collections import deque
dq=deque([])
topo=[]
for i in range(v):
    if incnt[i]==0:
        dq.append(i)
while dq:
    a=dq.popleft()
    for to in edges[a]:
        incnt[to]-=1
        if incnt[to]==0:dq.append(to)
    topo.append(a)
print(*topo,sep="\n")

Submission status: Accepted

Solution code:
from collections import deque
V,E = map(int,input().split())
G = [[] for _ in range(V)]
reached = [False]*V
indeg = [0]*V
for _ in range(E):
    s,t = map(int,input().split())
    G[s].append(t)
    indeg[t] += 1
out = []

def bfs(s):
    Q = deque()
    Q.append(s)
    reached[s] = True
    while Q:
        u = Q.popleft()
        out.append(u)
        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and reached[v] == False:
                reached[v] = True
                Q.append(v)

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

topologicalSort()
for i in out: print(i)

Submission status: Accepted

Solution code:
v, e = map(int, input().split())

adjacency_list = [[] for i in range(v)]

queue = []
deg = [0] * v

for _ in range(e):
    s, t = map(int, input().split())
    adjacency_list[s].append(t)
    deg[t] += 1
    
for i in range(v):
    if deg[i] == 0:
        queue.append(i)
        print(i)
        
while queue:
    vertex = queue.pop(0)
    for v in adjacency_list[vertex]:
        deg[v] -= 1
        if deg[v] == 0:
            queue.append(v)
            print(v)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_4_B
# 仕組みは単純ゆえに、本では解説がバッサリ省略されている。操作の可視化を行うと図のようになる。
# ここでは隣接リストを用いて実装する。

from collections import deque
# 隣接リストはdefaultdictで管理すると楽です。
from collections import defaultdict
adj = defaultdict(lambda: [])

# input data
n_V, n_E = list(map(int, input().split()))
indeg = [0] * n_V  # 流入量管理
for _ in range(n_E):
    s, t = list(map(int, input().split()))
    indeg[t] += 1  # 流入量更新
    adj[s].append(t)


# Topological Sort by BFS
def topological_sort(dag, indeg):
    '''
    dag ... default dictで定義された隣接リスト(DAGを想定)
    indeg ... 各ノードについての流入量のリスト(inputのときについでにやったほうが計算量若干少なく済むでしょ？本質じゃないけど)
    '''
    is_visited = [False] * len(indeg)  # 訪問間利用
    ret = []  # グラフをソートしたあとに返す答え
    perm = [-1] * len(indeg)  # できる処理を一気にしようとしたときの順番

    que = deque()  # 各要素はノード, 処理回数
    for i, deg in enumerate(indeg):
        if deg == 0:
            que.append((i, 0))
            is_visited[i] = True

    while que:
        u, cnt = que.popleft()  # uは流入量0のノード
        ret.append(u)  # なので答えに加えていく
        perm[u] = cnt
        for to in dag[u]:  # uに隣接するノードtoについて深さ優先探索
            indeg[to] -= 1  # 隣接するノードは流入量を減らす
            if indeg[to] or is_visited[to]:
                continue  # 流入待ちか訪問済みだったら飛ばす
            que.append((to, cnt + 1))  # 次の訪問候補に追加
            is_visited[to] = True

    if False in is_visited:
        print(is_visited)
        raise ValueError('inputted graph is not DAG')

    return ret, perm


ans, _ = topological_sort(adj, indeg)
print(*ans, sep='\n')