Problem:


Score : 500 points

Problem Statement

There is a rooted tree (see Notes) with N vertices numbered 1 to N.
Each of the vertices, except the root, has a directed edge coming from its parent.
Note that the root may not be Vertex 1.

Takahashi has added M new directed edges to this graph.
Each of these M edges, u \rightarrow v, extends from some vertex u to its descendant v.

You are given the directed graph with N vertices and N-1+M edges after Takahashi added edges.
More specifically, you are given N-1+M pairs of integers, (A_1, B_1), ..., (A_{N-1+M}, B_{N-1+M}), which represent that the i-th edge extends from Vertex A_i to Vertex B_i.

Restore the original rooted tree.

Notes

For "tree" and other related terms in graph theory, see the article in Wikipedia, for example.

Constraints

3 \leq N

1 \leq M

N + M \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

If i \neq j, (A_i, B_i) \neq (A_j, B_j).

The graph in input can be obtained by adding M edges satisfying the condition in the problem statement to a rooted tree with N vertices.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_{N-1+M} B_{N-1+M}

Output

Print N lines.
In the i-th line, print 0 if Vertex i is the root of the original tree, and otherwise print the integer representing the parent of Vertex i in the original tree.

Note that it can be shown that the original tree is uniquely determined.

Sample Input 1

3 1
1 2
1 3
2 3

Sample Output 1

0
1
2

The graph in this input is shown below:

It can be seen that this graph is obtained by adding the edge 1 \rightarrow 3 to the rooted tree 1 \rightarrow 2 \rightarrow 3.

Sample Input 2

6 3
2 1
2 3
4 1
4 2
6 1
2 6
4 6
6 5

Sample Output 2

6
4
2
0
6
2



Sample input:
3 1
1 2
1 3
2 3


Sample output:
0
1
2

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

#入力受け取り
def getlist():
	return list(map(int, input().split()))

N, M = getlist()
outE = defaultdict(list)
inE = defaultdict(int)

for i in range(N + M - 1):
	u, v = getlist()
	outE[u - 1].append(v - 1)
	inE[v - 1] += 1

Q = deque()
for i in range(N):
	if inE[i] == 0:
		Q.append(i)
top = []
while Q:
	v1 = Q.popleft()
	top.append(v1)
	for v2 in outE[v1]:
		inE[v2] -= 1
		if inE[v2] == 0:
			Q.append(v2)

parent = [0] * N
for i in top:
	for j in outE[i]:
		parent[j] = i + 1
for i in range(N):
	print(parent[i])

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())

dic = {}
npflag = [True] * N
pnum = [0] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False
    pnum[B] += 1

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)
                

for i in range(N):

    print (p[i]+1)

Submission status: Accepted

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

N, M = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(N-1+M):
    A, B = map(int,input().split())
    A -= 1; B -= 1
    to[A].append(B)
    fr[B].append(A)

# トポロジカルソート　計算量O(V+E)
# 有向グラフに用いる
# 閉路検出(DAGの判定)やDPの更新順序を明らかにするときなどに使える

# num[i] : iに入ってくる有効辺の本数
num = [0] * N

# グラフの構築でnumを更新しておく
num = [len(fr[v]) for v in range(N)]

S = deque()
L = []
#　例えば-1で初期化 dp = [-1] * N
'''  編集　'''

for v in range(N):
    if num[v] == 0:
        S.append(v)
        # 入次数0の頂点において例えば0で初期化　dp[v] = 0
        '''　編集　'''

while S:
    v = S.popleft()
    L.append(v)
    for nv in to[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
        # dpの更新　例えばmaxをとる dp[nv] = max(dp[nv], dp[v] + w[v])
        ''' 　編集 '''

# 閉路がある場合の処理
if len(L) != N:
    '''  編集　'''
    pass

index = [-1] * N
for i, v in enumerate(L):
    index[v] = i

for v in range(N):
    if v == L[0]:
        print(0)
        continue
    pv = -1
    d = N
    for cand in fr[v]:
        res = index[v] - index[cand]
        if res < d:
            d = res
            pv = cand
    pv += 1
    print(pv)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = []
children = [set() for _ in range(N)]
parents = [set() for _ in range(N)]
for _ in range(N+M-1):
    A, B = inpl()
    A -= 1
    B -= 1
    children[A].add(B)
    parents[B].add(A)

parent = [-1]*N
pool = list(range(N))
L = []
visited = [False]*N
while pool:
    i = pool.pop()
    if i >= N:
        L.append(i-N)
    elif visited[i]:
        continue
    else:
        visited[i] = True
        pool.append(i+N)
        for c in children[i]:
            pool.append(c)
L = L[::-1]
position = [None]*N
for i in range(N):
    position[L[i]] = i
for i in range(N):
    if not parents[i]:
        print(0)
    else:
        print(L[max(position[c] for c in parents[i])]+1)

Submission status: Accepted

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

n,m = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(n-1+m)]

graph = [[] for _ in range(n)]
indegree = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]

for i in range(n-1+m):
    graph[edge[i][0]-1].append(edge[i][1]-1)
    indegree[edge[i][1]-1] += 1

root = indegree.index(0)
parent[root] = 0

queue = deque()
queue.append(root)

while queue:
    node = queue.popleft()
    for adj in graph[node]:
        indegree[adj] -= 1
        if indegree[adj] == 0:
            queue.append(adj)
            parent[adj] = node+1

for p in parent:
    print(p)

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, M, *AB = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# その頂点の親の数
parents = [0] * (N + 1)
for A, B in zip(*[iter(AB)] * 2):
    graph[A].append(B)
    parents[B] += 1

answer = [0] * (N + 1)
n = parents[1:].index(0) + 1
queue = deque([n])

while queue:
    V = queue.popleft()

    for v in graph[V]:
        # vはVの子
        parents[v] -= 1

        if parents[v] == 0:
            # より根に近い頂点は全て調査済みなので、
            # V = 真の親である可能性のある頂点の中で最も若い親
            # このとき「書き足された各辺u→vは、ある頂点uからその子孫であるような頂点vに向かって伸びています。」を必ず満たせる
            queue.append(v)
            answer[v] = V

print(*answer[1:], sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N,M=map(int,input().split())
par=[[] for _ in range(N)]
for _ in range(N-1+M):
  a,b=map(int,input().split())
  par[b-1].append(a)

dep=[-1]*N
def depth(n):
  if dep[n-1]!=-1:
    return dep[n-1]
  else:
    if len(par[n-1])==0:
      dep[n-1]=0
      return 0
    else:
      dep[n-1]=max([depth(i) for i in par[n-1]])+1
      return dep[n-1]

for i in range(N):
  if len(par[i])==0:
    print(0)
  elif len(par[i])==1:
    print(par[i][0])
  else:
    m=-1
    a=par[i][0]
    for j in par[i]:
      d=depth(j)
      if m<d:
        m=d
        a=j
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    ro[b-1]+=1
for i in range(n):
    if ro[i]==0:
        r=i
ans=[0]*n
q=deque([r])
while len(q)>0:
    u=q.popleft()
    for v in g[u]:
        ro[v-1]-=1
        if ro[v-1]==0:
            ans[v-1]=u+1
            q.append(v-1)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
# 写経
# https://betrue12.hateblo.jp/entry/2019/01/28/215129
# http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
# https://atcoder.jp/contests/nikkei2019-qual/submissions/4112080

from collections import deque

n, m = map(int, input().split())
g = tuple(set() for _ in range(n))  # グラフの隣接リスト
ins = [0] * n  # 頂点の入次数を管理

for _ in range(n - 1 + m):
    s, t = (int(x) - 1 for x in input().split())
    # 頂点は0-indexedで管理する
    g[s].add(t)  # 頂点sから頂点tへの有向辺
    ins[t] += 1  # 入次数

root = -1  # 根の頂点番号（出力時の0-indexedから1-indexedへの変換（+1）で0になるようにとる）
dq = deque((v, root) for v in range(n) if ins[v] == 0)  # 入次数0の頂点の「番号vとその親root」
res = [-1] * n  # 親の頂点番号（0-indexedなので、出力時に1-indexedに直す）

while dq:
    v, root = dq.popleft()
    res[v] = root
    for u in g[v]:
        ins[u] -= 1  # 隣接する頂点の入次数をマイナス1
        if ins[u] == 0:
            dq.append((u, v))  # これによって入次数が0になればqに追加

res = (x + 1 for x in res)
print(*res, sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    to = defaultdict(set)
    ot = defaultdict(set)
    n, m = map(int, input().split())
    cnt_in_degree = [0] * n
    parent = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        cnt_in_degree[b] += 1
        to[a].add(b)
        ot[b].add(a)
    root = cnt_in_degree.index(0)
    parent[root] = -1
    part_roots = [root]
    cnt_decide = 1
    while cnt_decide < n:
        u = part_roots.pop()
        for ku in to[u]:
            if len(ot[ku]) == 1:
                parent[ku] = u
                part_roots.append(ku)
                cnt_decide += 1
            else:
                ot[ku].remove(u)
    for u in parent:
        print(u + 1)

main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
ie = dd(list)
inc = [0] * (N + 1)
for _ in range(N + M - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  ie[v].append(u)
  inc[v] += 1

def topologically(n, e, inc):
  res = []
  s = []
  c = 0
  many = 0
  for i in range(1, n + 1):
    if inc[i] == 0:
      s.append(i)
      c += 1
  many = c > 1
  while len(s):
    p = s.pop()
    res.append(p)
    for q in e[p]:
      inc[q] -= 1
      if inc[q] == 0:
        s.append(q)
    many = many or ((len(s) - c) > 0)
    c = len(s)
  return res
r = topologically(N, e, inc)
rrank = [0] * (N + 1)
#print(r)
for i in range(N):
  rrank[r[i]] = i
#print(rrank)
res = [0] * (N + 1)
for u in range(1, N + 1):
  t = -1
  for v in ie[u]:
    if rrank[v] > t:
      res[u] = v
      t = rrank[v]
for i in range(1, N + 1):
  print(res[i])

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
deg = [0]*N
parent = [[] for _ in range(N)]
for _ in range(N-1+M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
    deg[y-1] += 1
    parent[y-1].append(x-1)
    
from collections import deque
res = list(v for v in range(N) if deg[v] == 0)
q = deque(res)
while q:
    v = q.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t] == 0:
            q.append(t)
            res.append(t)
    
res.reverse()
f = [0]*N
for i in range(N):
    f[res[i]] = i
    
ans = [0]*N
for i in range(N):
    if parent[i]:
        temp = parent[i][0]
        for p in parent[i]:
            if f[temp] > f[p]:
                temp = p
        ans[i] = temp+1
        
for i in range(N):
    print(ans[i])

Submission status: Accepted

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


N, M = map(int, input().split())

graph = [[] for _ in range(N)]
num_of_parent = [0]*N
for _ in range(N+M-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    num_of_parent[b-1] += 1

for i in range(N):
    if num_of_parent[i] == 0:
        root = i
        break

Parent = [None]*N
Parent[root] = 0
q = [root]
while q:
    qq = []
    for p in q:
        for np in graph[p]:
            num_of_parent[np] -= 1
            if num_of_parent[np] == 0:
                Parent[np] = p+1
                qq.append(np)
    q = qq

for p in Parent:
    print(p)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N)]
G1= [[] for _ in range(N)]
H = [0]*N
for _ in range(N+M-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G1[b-1].append(a-1)
    H[b-1]+=1
def topological_sort(G, H):
    res = []
    st0 = set()
    for v, n in enumerate(H):
        if n == 0:
            st0.add(v)
    while st0:
        v = st0.pop()
        res.append(v)
        for nv in G[v]:
            H[nv]-=1
            if H[nv] == 0:
                st0.add(nv)
    return res
res = topological_sort(G, H)
index = [-1]*N
for i, v in enumerate(res):
    index[v] = i
ans = [-1]*N
for v in res[1:]:
    nv = max(G1[v], key = lambda x:index[x])
    ans[v] = nv+1
ans[res[0]] = 0
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
A,B=zip(*AB)
r=(set(range(1,N+1))-set(B)).pop()
def tsort():
    c=[[] for i in range(N)]
    t=[0]*N
    for i,j in AB:
        c[i-1].append(j-1)
        t[j-1]+=1
    s=[r-1]
    l=[]
    while len(s)>0:
        n=s.pop()
        l.append(n)
        for i in c[n]:
            t[i]-=1
            if t[i]==0:
                s.append(i)
    return l
cr=[[] for i in range(N)]
for i,j in AB:
    cr[j-1].append(i-1)
S=tsort()
o=[0]*N
for i,s in enumerate(S):
    o[s]=i
for i in range(N):
    x=-1
    for e in cr[i]:
        x=max(x,o[e])
    print(0 if x==-1 else S[x]+1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,M = II()
A,B = Line(N-1+M,2)

parent = [[] for _ in range(N)]
parent_num = [0]*N
pt = [[] for _ in range(N)]

for i in range(N-1+M):
    parent[B[i]-1].append(A[i]-1)
    parent_num[B[i]-1] += 1
    pt[A[i]-1].append(B[i]-1)

for i in range(N):
    if parent[i]==[]:
        root = i

ans = ['0']*N
q = [root]
while q:
    q_new = []
    for q1 in q:
        for v in pt[q1]:
            if parent_num[v]==1:
                ans[v] = q1+1
                q_new.append(v)
            parent_num[v] -= 1
    q = q_new

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

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(N)]
depth = [0 for _ in range(N)]
parent_list = [[] for _ in range(N)]
parent_num = [0 for _ in range(N)]
parent = [-1 for _ in range(N)]

for i in range(N - 1 + M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)
	parent_list[B].append(A)
	parent_num[B] += 1

for i in range(N):
	if len(parent_list[i]) == 0:
		root = i
		break

que = deque([])
que.append(root)

while len(que) > 0:
	node = que.popleft()
	if len(graph[node]) > 0:
		for edge in graph[node]:
			depth[edge] = depth[node] + 1
			parent_num[edge] -= 1
			if parent_num[edge] == 0:
				que.append(edge)

for i in range(N):
	parent_depth = -1
	parent_node = -1
	if len(parent_list[i]) > 0:
		for p in parent_list[i]:
			if depth[p] > parent_depth:
				parent_depth = depth[p]
				parent_node = p
		parent[i] = parent_node

#print(parent_list, depth)

for i in range(N):
	print(parent[i] + 1)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
g = [set() for _ in range(n+1)]
gg = [0]*(n+1)
for _ in range(n-1+m):
    a,b = map(int,input().split())
    g[a].add(b)
    gg[b] += 1
p = [-1]*(n+1)
q = deque()
for i in range(1,n+1):
  if gg[i] == 0:
    p[i] = 0
    q.append(i)
    break
while q:
  v = q.popleft()
  for x in g[v]:
    gg[x] -= 1
    if gg[x] == 0:
      q.append(x)
      p[x] = v
for x in p[1:]:
  print(x)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(node_num - 1 + edge_num)]

    parent_node = [0 for i in range(node_num + 1)]
    graph_data = defaultdict(set)
    nyuuji = [0 for i in range(node_num + 1)]

    for i in range(node_num - 1 + edge_num):
        a, b = data[i]
        graph_data[a].add(b)
        nyuuji[b] += 1

    root = -1
    for i in range(1, node_num + 1):
        if nyuuji[i] == 0:
            root = i

    now_set = set()
    next_set = set()
    now_set.add(root)

    while len(now_set):
        for now_node in now_set:
            for next_node in graph_data[now_node]:
                nyuuji[next_node] -= 1
                if nyuuji[next_node] == 0:
                    next_set.add(next_node)
                    parent_node[next_node] = now_node

        now_set = next_set
        next_set = set()

    for i in range(1, node_num + 1):
        print(parent_node[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
ans = [-1] * N

# 葉からの検索を行う
@lru_cache(maxsize=None)
def search(now):
    if now == root:
        ans[now] = 0
        return 0
    ret = -1
    for pr in parent[now]:
        depth = search(pr)
        if depth > ret:
            ans[now] = pr + 1
            ret = depth
    return ret + 1

for i in range(N):
    search(i)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())

L=[[]for i in range(N+1)]

I=[0 for i in range(N+1)]
for i in range(N+M-1):
    a,b=map(int,input().split())
    L[a].append(b)
    I[b]+=1
    
#print(L)
#print(I)
P=[-1 for i in range(N+1)]
S=-1
for i in range(1,N+1):
    if I[i]==0:
        P[i]=0
        S=i
        break

B=[]
cnt=0
for i in L[S]:
    if I[i]==1:
        B.append(i)
        P[i]=S
    else:
        I[i]-=1

for i in range(10**6):
    if cnt==len(B):
        break
    for j in L[B[cnt]]:
        if I[j]==1:
            B.append(j)
            P[j]=B[cnt]
        else:
            I[j]-=1
    cnt+=1
for i in range(1,N+1):
    print(P[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,m = map(int, input().split())
G = [[] for i in range(n)]
rG = [[] for i in range(n)]
used = [0]*n
for i in range(n+m-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    rG[b].append(a)
    used[b] = 1
root = used.index(0)

par = [-1]*n
depth = [-1]*n

def rec(cur):
    if depth[cur] != -1:
        return depth[cur]
    m = 0
    i = -1
    for p in rG[cur]:
        if rec(p)+1 > m:
            i = p
            m = rec(p)+1
    par[cur] = i
    depth[cur] = m
    return m

for i in range(n):
    rec(i)
par = [i+1 for i in par]
print(*par, sep="\n")

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()
    E = N+M-1
    edge = [set() for _ in range(N)]
    indegree = [0]*N
    for _ in range(E):
        a,b = MI_()
        edge[a].add(b)
        indegree[b]+=1
    
    queue = deque()
    for v in range(N):
        if not indegree[v]:
            queue.append(v)
    
    pop = queue.popleft
    ans = [0]*N
    topo_sort = []
    while queue:
        v = pop()
        topo_sort.append(v)

        for u in edge[v]:
            indegree[u]-=1
            if not indegree[u]:
                ans[u] = v + 1
                queue.append(u)
    print(*ans,sep="\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def topological_sort(N, edges):
    from collections import deque
    nps=[0]*N
    for _, dsts in enumerate(edges):
        for dst in dsts:
            nps[dst]+=1
    
    q = deque([])
    for i, np in enumerate(nps):
        if np==0:
            q.append(i)
    
    rets = [0]*N
    cnt=0
    while q:
        src = q.popleft()
        rets[src]=cnt
        cnt+=1
        for dst in edges[src]:
            nps[dst]-=1
            if nps[dst]==0:
                q.append(dst)
    return rets

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

for _ in range(N-1+M):
    a,b=map(int,input().split())
    edges[a-1].append(b-1)
    revedges[b-1].append(a-1)

inds = topological_sort(N, edges)
parents=[-1]*N
for dst in range(N):
    if len(revedges[dst])==0:
        parents[dst]=0
    else:
        _,parents[dst] = max([(inds[src],src+1) for src in revedges[dst]])

for p in parents:
    print(p)

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
edges=[[] for _ in range(N)]
nps=[0]*N

for _ in range(N-1+M):
    a,b=map(int,input().split())
    edges[a-1].append(b-1)
    nps[b-1]+=1

arr=[[]]

for i,np in enumerate(nps):
    if np==0:
        arr[-1].append(i)

while arr[-1]:
    arr.append([])
    for src in arr[-2]:
        for dst in edges[src]:
            nps[dst]-=1
            if nps[dst]==0:
                arr[-1].append(dst)

gens=[0]*N
for gen, a in enumerate(arr):
    for n in a:
        gens[n]=gen

parents=[-1]*N
q=deque(arr[0])
while q:
    src = q.popleft()
    for dst in edges[src]:
        if gens[dst]-gens[src]==1:
            parents[dst]=src+1
            q.append(dst)

for p in parents:
    print(p if p>0 else 0)

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(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


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

s = incnts.index(0)
ans = [-1]*N
ans[s] = -1

q = queue.Queue()
q.put(s)
while not q.empty():
    s = q.get()
    for t in lines[s]:
        incnts[t] -= 1
        if incnts[t] == 0:
            ans[t] = s
            q.put(t)

for a in ans:
    print(a+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N+M-1)]

out_edge = [set() for _ in range(N+1)]
in_edge = [set() for _ in range(N+1)]
for a,b in AB:
    out_edge[a].add(b)
    in_edge[b].add(a)

# topological sortを計算する
in_deg = [len(x) for x in in_edge]

q = [i for i,x in enumerate(in_deg[1:],1) if x == 0]

node_sorted = []
while q:
    x = q.pop()
    node_sorted.append(x)
    # xから出ている辺を削除
    for y in out_edge[x]:
        in_deg[y] -= 1
        if in_deg[y] == 0:
            q.append(y)

node_rank = {x:i for i,x in enumerate(node_sorted,1)}
node_rank[0] = 0

answer = [0] * (N+1)
for a,b in AB:
    # b の親をaにするか：rankが上なら
    if node_rank[answer[b]] < node_rank[a]:
        answer[b] = a

print('\n'.join(map(str,answer[1:])))

Submission status: Accepted

Solution code:
import sys
# from heapq import heappop, heappush
from collections import deque
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [0] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B) #無向グラフの作成
    check_lst[B] += 1 #その点に入って来る辺が何本あるかを数える

n = check_lst.index(0) #入って来る辺が無いとき、その頂点がスタート
ans = [0] * N #答えのリスト
que = deque()
q_append = que.append
q_append(n) #スタートをqueに入れる
q_left = que.popleft
while que:
    v = q_left()
    for v2 in lst[v]: #頂点vから出る辺について走査
        check_lst[v2] -= 1
        if check_lst[v2] == 0: #最後に出てきたものだけ考える
            q_append(v2)
            ans[v2] = v + 1

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

Submission status: Accepted

Solution code:
import sys
# from heapq import heappop, heappush
from collections import deque
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [0] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B)
    check_lst[B] += 1

n = check_lst.index(0)
ans = [0] * N
que = deque()
que.append(n)
while que:
    v = que.popleft()
    for v2 in lst[v]:
        check_lst[v2] -= 1
        if check_lst[v2] == 0:
            que.append(v2)
            ans[v2] = v + 1
print (*ans, sep = '\n')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [set() for _ in [0]*N]
E2 = [set() for _ in [0]*N]
Eb = [set() for _ in [0]*N]
for a,b in AB:
    E[a-1].add(b-1)
    E2[a-1].add(b-1)
    Eb[b-1].add(a-1)

p = [0]*N
q = []
for i in range(N):
    if not E[i]:
        q.append(i)
while q:
    qq = set()
    for i in q:
        for j in Eb[i]:
            E[j].remove(i)
    for i in q:
        while Eb[i]:
            j = Eb[i].pop()
            if not E[j]:
                for k in E2[j]:
                    if p[k] == 0 : p[k] = j+1
                qq.add(j)
    q = qq

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

Submission status: Accepted

Solution code:
def tpsort(es):
    n = len(es)
    indgr = [0] * n
    for e in es:
        for u in e:
            indgr[u] += 1
    st = [v for v in range(n) if indgr[v] == 0]
    parent = [0] * n
    while st:
        v = st.pop()
        for u in es[v]:
            indgr[u] -= 1
            if indgr[u] == 0:
                st.append(u)
                parent[u] = v
    return parent

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(N+M-1):
    a, b = map(int, input().split())
    es[a].append(b)
ans = tpsort(es)
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from collections import defaultdict,deque
OUT=defaultdict(set)
cnt=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    OUT[a]|={b}
    cnt[b]+=1
check=deque([i for i in range(N) if cnt[i]==0])
ans=[N]*N
ans[check[0]]=0
while len(check)>0:
    now=check.popleft()
    for nex in OUT[now]:
        cnt[nex]-=1
        if cnt[nex]==0:
            ans[nex]=now+1
            check.append(nex)
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

# 入力
N, M = map(int, input().split())
A, B = zip(*(map(int, input().split()) for _ in range(N - 1 + M)))

# 各頂点の深さを求め、深さを利用して元の木を復元する
G = [set() for _ in range(N + 1)]
G_inv = [set() for _ in range(N + 1)]
for a, b in zip(A, B):
    G[a].add(b)
    G_inv[b].add(a)
deg = [len(G_inv[i]) for i in range(N + 1)]
V = [i for i in range(1, N + 1) if not G_inv[i]]
deq = deque(V)
while deq:
    i = deq.popleft()
    for j in G[i]:
        deg[j] -= 1
        if deg[j] == 0:
            deq.append(j)
            V.append(j)

R = {i: r for r, i in enumerate(V)}
ans = '\n'.join(
    str(max(G_inv[i], key=lambda j: R[j], default=0))
    for i in range(1, N + 1)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
start={i for i in range(N) if IN[i]==0}
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
[print(p) for p in P]

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
Ans=[0]*(n+1)
Children=[[] for _ in range(n+1)]
Cnt=[0]*(n+1); Cnt[0]=1
for _ in range(n+m-1):
    a,b=map(int,input().split())
    Children[a].append(b)
    Cnt[b]+=1
root=Cnt.index(min(Cnt))
V=[root]
while V:
    v=V.pop()
    for u in Children[v]:
        if Cnt[u]==1:
            Ans[u]=v
            V.append(u)
        else:
            Cnt[u]-=1
print(*Ans[1:],sep='\n')

Submission status: Accepted

Solution code:
import collections

N, M = map(int, input().split())

ans = [0] * (N + 1)
parent = [0] * (N + 1)
parent[0] = N+M
child = [[] for i in range(N+1)]
deq = collections.deque()

for i in range(N+M-1):
    p, c = map(int, input().split())
    parent[c] += 1
    child[p].append(c)
root = parent.index(min(parent))
deq.append(root)
while len(deq) > 0:
    v = deq.pop()
    if len(child[v]) > 0:
        for u in child[v]:
            if parent[u] == 1:
                deq.appendleft(u)
                ans[u] = v
            else:
                parent[u] -= 1
for i in range(1,N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
x,y = [[] for i in range(n+1)],[0]*(n+1)
y[0] = 1
for i in range(n+m-1):
    a,b = (int(i) for i in input().split())
    x[a].append(b)
    y[b]+=1
ans,q = [0]*(n+1),[y.index(0)]
while q:
    p = q.pop()
    for i in x[p]:
        y[i]-=1
        if not y[i]:
            q.append(i)
            ans[i] = p
for i in ans[1:]: print(i)