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:
# -*- coding: utf-8 -*-
from sys import stdin
# import sys
# sys.setrecursionlimit(10 ** 5+1)
import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


from collections import deque
def topological_sort(graph, nodes):
    """

    Prameters
    ---------
    graph: list, [[parent, child], ...]
        graph[i][0]からgraph[i][1]へ
        コード上はv1が親ノード,v2が子ノード

    nodes : list
        全ノードのリスト

    Returns
    -------
    res : list
        トポロジカルソートされたノード
        インデックスが小さい方が親ノード側
    """
    outs = {i: [] for i in nodes}
    ins = {i: 0 for i in nodes}
    for v1, v2 in graph:
        outs[v1].append(v2)
        ins[v2] += 1

    queue = deque(i for i in nodes if ins[i] == 0)
    res = []
    while queue:
        v1 = queue.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                queue.append(v2)
    return res


N, M = ds_in()

parent = {i+1: [] for i in range(N)}
graph = []
for _ in range(N+M-1):
    a, b = ds_in()
    graph.append([a, b])
    parent[b].append(a)

res = topological_sort(graph, [i+1 for i in range(N)])

sorted_index = np.zeros(N+1, dtype=int)
sorted_index[res] = np.arange(N)

for i in range(1, N+1):
    if i == res[0]:
        print(0)
    else:
        print(parent[i][np.argmax(sorted_index[parent[i]])])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import sys
# sys.setrecursionlimit(10 ** 5+1)
import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

child = {i+1: [] for i in range(N)}
parent = {i+1: [] for i in range(N)}
inflow = {i+1: 0 for i in range(N)}
for _ in range(N+M-1):
    a, b = ds_in()
    child[a].append(b)
    parent[b].append(a)
    inflow[b] += 1

candidates = []
for i, j in inflow.items():
    if j == 0:
        candidates.append(i)

sorted_edges = []
while len(sorted_edges) < N:
    par = candidates.pop()
    sorted_edges.append(par)
    for chi in child[par]:
        inflow[chi] -= 1
        if inflow[chi] == 0:
            candidates.append(chi)


sorted_index = np.zeros(N+1, dtype=int)
sorted_index[sorted_edges] = np.arange(N)

for i in range(1, N+1):
    if i == sorted_edges[0]:
        print(0)
    else:
        print(parent[i][np.argmax(sorted_index[parent[i]])])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+1)
n,m = map(int,input().split())
tree = [[] for i in range(n)]
tree_rev = [[] for i in range(n)]
for i in range(n-1+m):
    x, y = map(int, input().split())
    tree[x-1].append(y-1)
    tree_rev[y-1].append(x-1)
# topological_sorted_n : トポロジカル順序に並んだリスト
topological_sorted_n = []
visited = [False]*n

def topological_sort(i):
    if not visited[i]:
        visited[i] = True
        for next_i in tree[i]:
            topological_sort(next_i)
        topological_sorted_n.append(i)

for i in range(n):
    topological_sort(i)
topological_sorted_n = topological_sorted_n[::-1]

memo = {}
for i in range(n):
    memo[topological_sorted_n[i]] = i

for i in range(n):
    index = -1
    ans = 0
    for pos in tree_rev[i]:
        if index < memo[pos]:
            index = memo[pos]
            ans = pos+1
    print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    par = [[] for _ in range(N)]
    chi = [[] for _ in range(N)]
    root = None
    for i in range(N + M - 1):
        chi[A[i] - 1].append(B[i] - 1)
        par[B[i] - 1].append(A[i] - 1)

    #print(chi)
    #print(par)
    for i in range(N):
        if len(par[i]) < 1:
            root = i
            par[i].append(-1)
            break

    cur = {root}
    while len(cur) > 0:
        #print(cur)
        nex = set()
        for idx in cur:
            for c in chi[idx]:
                if len(par[c]) < 2:
                    nex.add(c)
                else:
                    par[c].remove(idx)
        cur = nex

    for i in range(N):
        ret = par[i][0]
        print(ret + 1)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N-1+M)  # type: "List[int]" 
    B = [int()] * (N-1+M)  # type: "List[int]" 
    for i in range(N-1+M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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


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]


topological_order = topological_sort(G)


# 根からの最長経路を計算
dist = [-float('inf')] * N
dist[topological_order[0]] = 0
for n in topological_order:
    for to in G[n]:
        dist[to] = max(dist[to], dist[n] + 1)


ans = [-1] * N
for n in range(N):
    for to in G[n]:
        if dist[n] + 1 == dist[to]:
            ans[to] = n

for p in ans:
    print(p + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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


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]


topological_order = topological_sort(G)


# 根からの最長経路を計算
dist = [-float('inf')] * N
dist[topological_order[0]] = 0
for n in topological_order:
    for to in G[n]:
        dist[to] = max(dist[to], dist[n] + 1)


node_depth = sorted(list(enumerate(dist)), key=lambda x: x[1])
ans = [[node_depth[0][0], -1]]
for n, depth in node_depth:
    for to in G[n]:
        if dist[to] == depth + 1:
            ans.append([to, n])

ans.sort()
for i, p in ans:
    print(p + 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def dfs(graph, nd, toprogy, is_visited):
    is_visited.add(nd)
    for adj in graph[nd]:
        if adj not in is_visited:
            dfs(graph, adj, toprogy, is_visited)

    toprogy.appendleft(nd)

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    inv_graph = {}
    for i in range(1, N + 1):
        graph[i] = []
        inv_graph[i] = []

    for i in range(N - 1 + M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)
        inv_graph[b].append(a)

    sys.setrecursionlimit(200000)
    toprogy = deque([])
    is_visited = set([])
    for i in range(1, N + 1):
        if i not in is_visited:
            dfs(graph, i, toprogy, is_visited)

    toprogical_order = {}
    for i in range(N):
        toprogical_order[toprogy[i]] = i + 1

    for i in range(1, N + 1):
        max_toprogy = 0
        true_parent = 0
        for pare in inv_graph[i]:
            if pare not in toprogical_order:
                continue
            if max_toprogy < toprogical_order[pare]:
                max_toprogy =toprogical_order[pare]
                true_parent = pare
        print true_parent

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
for s in range(n):
    if not oya[s]:break
q=[[s,ko[s]]]
ans=[0]*n
while q:
    now,nex=q.pop()
    for i in nex:
        oya[i].remove(now)
        if not oya[i]:
            ans[i]=now+1
            q.append([i,ko[i]])
for i in ans:print(i)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
adjL = [[] for v in range(N)]
indegs = [0] * N
for _ in range(N+M-1):
    u, v = map(int, input().split())
    adjL[u-1].append(v-1)
    indegs[v-1] += 1

parents = [-1] * N
Q = deque([v for v in range(N) if indegs[v] == 0])
while Q:
    vNow = Q.popleft()
    for v2 in adjL[vNow]:
        parents[v2] = vNow
        indegs[v2] -= 1
        if indegs[v2] == 0:
            Q.append(v2)

for v in range(N):
    print(parents[v] + 1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

# 辺を保持しつつ根を見つける
edge = [set() for _ in range(N+1)]
indim = [0] * (N+1)
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
  indim[b] += 1
root = parent.index(0)

# 根から幅優先でたどっていく
ans = [-1] * (N+1)
q = set([root])
while len(q):
  nq = set()
  for p in q:
    for c in edge[p]:
      indim[c] -= 1
      if indim[c] == 0:
        nq.add(c)
        ans[c] = p
  q = nq

for i in range(1, N+1):
  print(ans[i] if ans[i] > 0 else 0)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())

fromR = {i:[] for i in range(N+1)}

cnt = [0 for i in range(N+1)]
ans = [-1 for i in range(N+1)]

for _ in range(N-1+M):
    a,b=map(int,input().split())
    fromR[a].append([b,a])
    cnt[b]+=1
r=-1
for i in range(1,N+1):
    if cnt[i]==0:
        r=i
        break

ans[r]=0

que = fromR[r]

while len(que)>0:
    tmp=[]
    for q in que:
        b,a=q
        cnt[b]-=1
        if cnt[b]==0:
            ans[b]=a
            tmp+=fromR[b]
    que=tmp
for a in ans[1:]:
    print(a)

Submission status: Accepted

Solution code:
def get_ans(pairs, n):
    prs = {i:set() for i in range(1, n+1)}
    chd = {i:set() for i in range(1, n+1)}
    for a, b in pairs:
        prs[b].add(a)
        chd[a].add(b)

    root = None
    for i in prs:
        if len(prs[i]) == 0:
            root = i
            break
    assert root is not None

    dir_pr = {root:0}
    q = [root]
    while len(q) > 0:
        p = q.pop()
        for c in chd[p]:
            prs[c].remove(p)
            if len(prs[c]) == 0:
                q.append(c)
                dir_pr[c] = p

    for i in range(1, n+1):
        print(dir_pr[i])


if __name__ == '__main__':
    n, m = map(int, input().split())
    ps = []
    for i in range(n+m-1):
        ps.append(tuple(int(x) for x in input().split()))
    get_ans(ps, n)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
v,n=map(int,input().split())
n+=v-1
es=[[int(x)-1for 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=[]
p=[0]*v
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
            p[v2]=v1+1
for t in p:print(t)

Submission status: Accepted

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# トポロジカルソート(頂点数、辺集合(DAG, 0-indexed))
def topological_sort(N: int, edges: list) -> list:
    # ここからトポロジカルソート準備
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(edges)):
        # 流入するノード数
        incnts[edges[i][1]] += 1
        # 流出先ノードのリスト
        outnodes[edges[i][0]].append(edges[i][1])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    i = 0
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            if incnts[node] == 0:
                S.add(node)
        # 各頂点が何番目かを保持しておく
        ts2[L[-1]] = i
        i += 1
    # ソートされた頂点のリストを返却
    return L

N, M = MAP()
edges = [None] * (N+M-1)
nodes2 = [[] for i in range(N)]
for i in range(N+M-1):
    u, v = MAP()
    edges[i] = (u-1, v-1)
    # node[到着点] = 出発点 の隣接リスト
    nodes2[v-1].append(u-1)

ts2 = [0] * N
ts = topological_sort(N, edges)

ans = [-1] * N
for v in range(N):
    mx = -1
    for u in nodes2[v]:
        # トポソ順で自分に近い(大きい)方を優先して残す
        if mx < ts2[u]:
            mx = ts2[u]
            ans[v] = u

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

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N + M - 1)]

# find start node
E = [[] for i in range(N)]
nE = [0] * N
for A, B in AB:
    E[A - 1].append(B)
    nE[B - 1] += 1

# print("#", E)
# print("#", nE)
    
S = []
for i in range(N):
    if nE[i] < 1: S.append(i + 1)

# print("#", S)
    
L = []
while len(S) > 0:
    Si = S.pop()
    L.append(Si)
    # print("##", Si)
    for Eij in E[Si - 1]:
        if nE[Eij - 1] == 1: S.append(Eij)
        nE[Eij - 1] -= 1
    else:
        E[Si - 1] = []

# print("#", L)

mapL = [0] * N
for i, Li in enumerate(L): mapL[Li - 1] = i + 1

ans = [0] * N
for Ai, Bi in AB:
    # print("##", Ai, Bi, ans[Bi - 1], mapL[Bi - 1])
    if ans[Bi - 1] < 1 or mapL[ans[Bi - 1] - 1] < mapL[Ai - 1]: ans[Bi - 1] = Ai

for ansi in ans: print(ansi)

Submission status: Accepted

Solution code:
import sys
from collections import deque

n,m=map(int,sys.stdin.readline().split()) 
al,cnt=[[] for _ in range(n)],[0]*n
for i in range(n+m-1):
    a,b=map(int,sys.stdin.readline().split())
    al[a-1].append(b-1)
    cnt[b-1] += 1
ans = [0]*n
que = deque()

# children = []
# child = 0
# for i in range(n):
#     if len(children) == 0:        
#         children = set(cnf)-set(bl)
#         parent = child
 
#     child = children.pop()
    
#     j = 0
#     while j < len(al):
#         if al[j] == child:
#             al.pop(j)
#             bl.pop(j)
#         else:
#             j += 1
#     ans[child-1] = parent
#     cnf.remove(child)

for i in range(n):
    if  cnt[i] == 0:
        que.append(i)
        break

while que:
    p = que.popleft()
    
    for j in al[p]:
        cnt[j] -= 1
        if cnt[j] == 0:
            que.append(j)
            ans[j]=p + 1

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split()) 

I=[ 0 for i in range(N+1) ]   #In: Nyujisuu
nl=[ []  for i in range(N+1) ] 

for i in range(N-1+M):
	a,b=map(int, sys.stdin.readline().split())
	I[b]+=1
	nl[a].append(b)


q=deque([])
start=I[1:].index(0)+1
q.append(start)

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

while q:
	n=q.popleft()
	for m in nl[n]:
		I[m]-=1
		if I[m]==0:
			q.append(m)
			par[m]=n


for x in par[1:]:
	print x

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
v, n = map(int, input().split())
n += v-1
es = [tuple(map(int, 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 not ins[v1])
res = []
p = [0]*(v+1)
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
            p[v2] = v1

for t in p[1:]:
    print(t)

Submission status: Accepted

Solution code:
from collections import deque

n,m = [int(i) for i in input().split() ]
child = list(list([]) for i in range(n))
count = list( 0 for i in range(n))
ans = list( -1 for i in range(n))
for i in range(n-1+m):
    x = [int(i) for i in input().split() ]
    y = x[0] - 1
    z = x[1] - 1
    child[y].append(z)
    count[z] += 1

root =count.index(0)
que=deque()
que.append(root)

new_child = list([])
while len(que)>0 :
    m = que.popleft()
    new_child.clear()
    for i, node in enumerate(child[m]):
        if count[node] == 1:
            que.append(node)
            ans[node] = m
            new_child.append(node)
        else:
            count[node] -= 1
    child[m] = new_child[:]

for i in ans:
    print(i+1)

Submission status: Accepted

Solution code:
from collections import deque

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

up = [[] for _ in range(n)] # [[]]*nした後にappendするのはNG
down = [[] for _ in range(n)]
used = [0]*n # これならOK
res = [0]*n
cnt = 0

for _ in range(n+m-1):
    p, c = map(int, input().split())
    up[c-1].append(p)
    down[p-1].append(c)

for i in range(n):
    if up[i] == []:
        root = i+1
        res[root-1] = 0
        used[root-1] = 1
        cnt += 1
        break

ptank = deque([root])
ctank = deque([root])
clist = list()

def is_p_used(i):
    for j in up[i-1]:
        if used[j-1]==0:
            return False
    return True

def find_c(p):
    for i in down[p-1]:
        if (is_p_used(i)) & (used[i-1]==0):
            res[i-1] = p
            ctank.append(i)
            clist.append(i)

while cnt < n:
    ptank = ctank
    ctank = deque()
    while len(ptank) != 0:
        find_c(ptank.popleft())
    cnt += len(ctank)
    for i in clist:
        used[i-1] = 1
    clist = list()
    

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
ab = []
for _ in range(N + M - 1):
    ab.append(tuple(map(int, input().split())))

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

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

order = [i for i, v in sorted(enumerate(res), key=lambda x: x[1])]

ans = [0] * N
ans[res[0]] = 0
for v in res[:0:-1]:
    ans[v] = max([(order[v2], v2) for v2 in rev[v]])[1] + 1

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

from collections import defaultdict

nodes = list(range(1, N + 1))
edges = defaultdict(set)
rev_edges = defaultdict(set)

for a, b in AB:
    edges[a].add(b)
    rev_edges[b].add(a)

#print(vs)
#print(ws)

def TopologicalSort(nodes, edges, rev_edges):
    '''
    nodes     ... Node[]
    edges     ... Dict[From Node](To Node)
    rev_edges ... Dict[To Node](From Node)
    '''
    rev_edges_num = dict((n, len(rev_edges[n])) for n in nodes)
    L = []
    S = [n for n in nodes if not rev_edges_num[n]]
    while S:
        n = S.pop()
        L.append(n)
        for m in edges[n]:
            rev_edges_num[m] -= 1
            if not rev_edges_num[m]:
                S.append(m)
    
    # プロコン用なのでエラーチェックはしない

    return L

L = TopologicalSort(nodes, edges, rev_edges)

nrank = dict((n, r) for r, n in enumerate(L))

for n in range(1, N + 1):
    r = 0
    if rev_edges[n]:
        r = sorted(rev_edges[n], key=lambda x:nrank[x], reverse=True)[0]
    print(r)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

from collections import defaultdict
from copy import deepcopy

vs = defaultdict(set)
ws = defaultdict(set)
rws = defaultdict(int)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)
    rws[b] += 1

#print(vs)
#print(ws)

# topological sort

L = []
S = [i for i in range(1, N + 1) if not rws[i]]

while S:
    n = S.pop()
    L.append(n)
    for m in vs[n]:
        rws[m] -= 1
        if not rws[m]:
            S.append(m)

#print(S)
#print(L)

nrank = dict((n, r) for r, n in enumerate(L))

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:-nrank[x])[0]
    print(r)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

import sys
sys.setrecursionlimit(100000)

from collections import defaultdict

vs = defaultdict(set)

for a, b in AB:
    vs[b].add(a)

cache = {}

def calc(n):
    if n in cache:
        return cache[n]
    max_distance = 0
    max_distance_parent = 0
    for m in vs[n]:
        d = calc(m)[0]
        if max_distance < d + 1:
            max_distance = d + 1
            max_distance_parent = m
    result = max_distance, max_distance_parent
    cache[n] = result
    return result

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

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

import sys
sys.setrecursionlimit(100010)

from collections import defaultdict

vs = defaultdict(set)

for a, b in AB:
    vs[b].add(a)

cache = {}

def calc(n):
    if n in cache:
        return cache[n]
    max_distance = 0
    max_distance_parent = 0
    for m in vs[n]:
        d = calc(m)[0]
        if max_distance < d + 1:
            max_distance = d + 1
            max_distance_parent = m
    result = max_distance, max_distance_parent
    cache[n] = result
    return result

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

Submission status: Accepted

Solution code:
def main():
  N, M = list(map(int, input().split()))
  inN = [0 for i in range(N)]
  outN = [[] for i in range(N)]
  
  for i in range(N + M - 1):
    Data = list(map(int, input().split()))
    inN[Data[1] - 1] += 1
    outN[Data[0] - 1].append(Data[1] - 1)
  
  D = []
  for i in range(N):
    if inN[i] == 0:
      D.append(i)
      
  L = []
  while D != []:
    t = D.pop()
    L.append(t)
    for i in outN[t]:
      inN[i] -= 1
      if inN[i] == 0:
        D.append(i)
   
  Ans = [0 for i in range(N)]
  for i in L:
    for j in outN[i]:
      Ans[j] = i + 1
      
  for i in Ans:
    print(i)
main()

Submission status: Accepted

Solution code:
from collections import deque
from operator import itemgetter


def topolo():
    q = deque(v1 for v1 in range(N) if ins[v1] == 0)
    res = []
    popleft, append = q.popleft, q.append
    res_append = res.append
    while q:
        v1 = popleft()
        res_append(v1)
        for v2 in edges[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                append(v2)
    return res


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

ins = [0]*N

for a, b in (map(int, input().split(" ")) for _ in [0]*(N+M-1)):
    edges[a-1].append(b-1)
    rev[b-1].append(a-1)
    ins[b-1] += 1

sorted_nodes = topolo()
order = [i for i, v in sorted(enumerate(sorted_nodes), key=itemgetter(1))]

for input_nodes in rev:
    l = len(input_nodes)
    if l == 0:
        print(0)
        continue
    elif l == 1:
        print(input_nodes[0] + 1)
        continue
    temp = 0
    for node in input_nodes:
        temp = max(temp, order[node])
    print(sorted_nodes[temp] + 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(n-1+m)]
indeg_n=[0]*n
indeg=[[]for i in range(n)]
outdeg=[[]for i in range(n)]
for a,b in src:
  indeg_n[b]+=1
  indeg[b].append(a)
  outdeg[a].append(b)
root=indeg_n.index(0)
toposo=[]
stack=[root]

while stack:
  v=stack.pop()
  toposo.append(v)
  for to in outdeg[v]:
    indeg_n[to]-=1
    if indeg_n[to]==0:
      stack.append(to)
order=[-1]*n
for i,v in enumerate(toposo):
  order[v]=i
ans=[-1]*n
ans[root]=0
for ti in range(1,n):
  v=toposo[ti]
  maxo=max(order[p] for p in indeg[v])
  ans[v]=toposo[maxo]+1
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = {i:[] for i in range(N)}
rG = {i: [] for i in range(N)}
X = [0]*(N)
searched = [0]*(N)

for _ in range(N-1+M):
    a, b = inpl()
    G[a-1].append(b-1)
    rG[b-1].append(a-1)
    X[b-1] += 1

q = X.index(0)
T = [0]*N
Q = deque([q])
t = 0
while Q:
    p = Q.popleft()
    T[p] = t
    t += 1
    for q in G[p]:          
        X[q] -= 1
        if X[q] == 0:
            Q.append(q)

for i in range(N):
    c, ans = -1, 0
    for p in rG[i]:
        if c < T[p]:
            c, ans = T[p], p+1
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

N, M = map(int, input().split())
BtoA = [[] for i in range(N + 1)]


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

memo = {}
def depth(b):
    if b in memo:
        return memo[b]
    
    res = 0
    for a in BtoA[b]:
        res = max(res, depth(a) + 1)

    memo[b] = res
    return res

for i in range(1, N + 1):
    ans = 0
    for a in BtoA[i]:
        if depth(a) + 1 == depth(i):
            ans = a
            break
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
edge = {}
inl = [0]*(n+1)
for _ in range(n-1+m):
    a,b = map(int, input().split())
    if a not in edge:
        edge[a] = []
    edge[a].append(b)
    inl[b] += 1

s = []
for v in range(1,n+1):
    if inl[v]==0:
        s.append(v)

l = []
res = [0]*(n+1)
while len(s)>0:
    v = s.pop()
    l.append(v)
    if not v in edge:
        continue
    for u in edge[v]:
        inl[u] -= 1
        if inl[u]==0:
            res[u] = v
            s.append(u)

for i in range(1,n+1):
    print(res[i])

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 i in range(N-1+M)]

#トポロジカルソートを使う方法
EDGEIN=[0]*(N+1)#その点に入るEDGEの個数
EDGEOUTLIST=[[] for i in range(N+1)]#EDGEの行き先
EDGEINLIST=[[] for i in range(N+1)]
ANSLIST=[-1]*(N+1)

for x,y in EDGE:
    EDGEIN[y]+=1
    EDGEOUTLIST[x].append(y)
    EDGEINLIST[y].append(x)

from collections import deque
QUE = deque()

for i in range(1,N+1):
    if EDGEIN[i]==0:
        QUE.append(i)#行き先のない点をQUEに入れる
        ANSLIST[i]=0
        
TOP_SORT=[]
while QUE:
    x=QUE.pop()
    TOP_SORT.append(x)#行き先がない点を答えに入れる
    for to in EDGEOUTLIST[x]:
        EDGEIN[to]-=1#行き先がない点を削除し,そこから一歩先の点のEDGEINを一つ減らす.
        if EDGEIN[to]==0:
            QUE.appendleft(to)

TOP_SORT_INV=[-1]*(N+1)
for i in range(N):
    TOP_SORT_INV[TOP_SORT[i]]=i

for i in range(1,N+1):
    if EDGEINLIST[i]==[]:
        continue
    
    ANSLIST[i]=TOP_SORT[max([TOP_SORT_INV[j] for j in EDGEINLIST[i]])]

for a in ANSLIST[1:]:
    print(a)

Submission status: Accepted

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

n,m = getNM()
children = [[] for i in range(n+2)]
n_in = [0] * (n+1)
par_origin = [0] * (n+1)

#入力の処理
for i in range(n+m-1):
    a,b = getNM()
    children[a].append(b)
    n_in[b] += 1

#根を見つける
for i in range(1,n+m-1):
    if n_in[i]:
        pass
    else:
        root = i
        break

#次数を減らしながら探索
import queue
def bfs(root):
    q = queue.Queue()
    q.put(root)
    while(True):
        try:
            cur = q.get(block=False)
        except:
            break
        for c in children[cur]:
            if n_in[c] == 1:
                par_origin[c] = cur
                q.put(c)
            else:
                n_in[c] -= 1

bfs(root)
for i in range(1, n+1):
    print(par_origin[i])