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

import sys
from collections import deque, defaultdict
from operator import itemgetter

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


# def topological_sort(graph: list, indegree: list):
#     from collections import deque
#     que = deque(i for i in range(len(graph)) if indegree[i] == 0)
#     order = []
#     while que:
#         v = que.popleft()
#         order.append(v)
#         for next in graph[v]:
#             indegree[next] -= 1
#             if indegree[next] == 0:
#                 que.append(next)
#
#     return order


n, m = LI()

G = [[] for _ in range(n)]
indegree = [0] * n

for _ in range(n + m - 1):
    a, b = LI_()
    G[a].append(b)
    indegree[b] += 1

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

ans = [0] * n
while que:
    v = que.popleft()
    for v2 in G[v]:
        indegree[v2] -= 1
        if indegree[v2] == 0:
            que.append(v2)
            ans[v2] = v + 1

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import deque
from operator import itemgetter

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()

G = [[] for _ in range(n)]
RG = [[] for _ in range(n)]
indegree = [0] * n

for _ in range(n + m - 1):
    a, b = LI_()
    G[a].append(b)
    RG[b].append(a)
    indegree[b] += 1

# Topological sort
que = deque()
for i in range(n):
    if indegree[i] == 0:
        que.append(i)

res = []
while que:
    v = que.popleft()
    res.append(v)
    for v2 in G[v]:
        indegree[v2] -= 1
        if indegree[v2] == 0:
            que.append(v2)

# 親の候補が複数ある場合
# 木の高さが最大になるような候補を選ぶ
# -> トポロジカル順序で最も後ろにある候補を選ぶ
order = [i for i, n in sorted(enumerate(res), key=itemgetter(1))]
for i in range(n):
    if len(RG) == 0:
        print(0)
        continue

    parent = -1
    d = -1
    for j in RG[i]:
        if order[j] > d:
            parent = j
            d = order[j]

    print(parent + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,m=map(int,input().split())
e=[]
tu=[[] for x in range(n+1)]
d=[0]*(n+1)
fa=[0]*(n+1)
for i in range(n-1+m):
    u,v=map(int,input().split())
    e.append((u,v))
    tu[u].append(v)
    d[v]+=1

def dfs(x):
    if x in vis:
        return
    vis.add(x)
    for t in tu[x]:
        dfs(t)
    tp.append(x)

vis=set()
tp=[]
for i in range(1,n+1):
    if d[i]==0:
      dfs(i)

d=[0]*(n+1)
tp.reverse()
for i in tp:
    for t in tu[i]:
        d[t]=max(d[t],d[i]+1)

for i in e:
    u,v=i
    if d[u]+1==d[v]:
        fa[v]=u

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

Submission status: Accepted

Solution code:
import queue

n,m=map(int,input().split())
fromto=[list(map(int,input().split()))for _ in range(n+m-1)]
m += n-1
fr = [[]for _ in range(n+1)]
to = [0]*(n+1)
ans = [0]*(n+1)
for f,t in fromto:
    fr[f].append(t)
    to[t]+=1
for i in range(1,n+1):
    if to[i] is 0:
        root = i
q=queue.Queue()
q.put(root)
while not q.empty():
    now = q.get()
    for nex in fr[now]:
        to[nex] -= 1
        if to[nex] is 0:
            ans[nex] = now
            q.put(nex)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

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)

queue = deque([i for i in range(N) if in_cnt[i] == 0])
sorted_ans = []

while len(queue) != 0:
    v1 = queue.popleft()
    sorted_ans.append(v1)
    for v2 in outs[v1]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

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

ans = [0] * N
ans[sorted_ans[0]] = 0
for v in sorted_ans[: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:
import queue
N,M =[int(i)for i in input().split()]
adlist =[[]for i in range(N)] #隣接リスト
oyalist =[[]for i in range(N)] #親ノードリスト
for _ in range(N+M-1):
    A,B =[int(i)-1 for i in input().split()]
    adlist[A].append(B)
    oyalist[B].append(A)

iri =[0]*N #入次数のリスト
for i in range(N):
    iri[i] =len(oyalist[i])

topo =[0]*N #トポロジカルソートの番号
tyouten =oyalist.index([]) #頂点
num = 0 #ソート番号
q =queue.Queue()
q.put(tyouten)
topo[tyouten]=num

while num != N-1:
    now = q.get()
    for i in adlist[now]:
        iri[i] -=1
        if iri[i] == 0:
            q.put(i)
            num += 1
            topo[i] =num

#出力
oyalist[tyouten].append(-1)
for i in range(N):
    oyalist[i] =sorted(oyalist[i],key=lambda x:topo[x],reverse=True)
    print(oyalist[i][0]+1)

Submission status: Accepted

Solution code:
from collections import deque

def resto(n,m,ab):

    oya=[[] for _ in range(n)]
    ko=[[] for _ in range(n)]

    for i,y in ab:
        oya[y-1]+=[i-1]
        ko[i-1]+=[y-1]

    root=0
    for i in range(n+m):
        if len(oya[i])==0:
            root=i
            break

    oya[root]=['a']
    deq=deque([root])
    while len(deq)>0:
        z=deq.popleft()
        for i in ko[z]:
            if len(oya[i])!=1:
                oya[i].remove(z)
            else:
                deq.append(i)

    ans=[str(0)+'\n' if i[0]=='a' else str(i[0]+1)+'\n' for i in oya ]

    return ''.join(ans)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Pcan = defaultdict(lambda: 0)

Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
    Pcan[B-1] += 1
par = list(Par)[0]
dist = [0]*N
Q = deque([par])

while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if Pcan[en] == 1:
                Q.append(en)
            else:
                Pcan[en] -= 1
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)

Submission status: Accepted

Solution code:
# http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
# https://atcoder.jp/contests/nikkei2019-qual/submissions/4112080

from collections import deque, defaultdict

V, E = map(int, input().split())
g = defaultdict(set)
# グラフの隣接リスト
h = defaultdict(int)
# 頂点の入次数を管理

for _ in range(V - 1 + E):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    # 頂点は0-indexedで管理する
    g[s].add(t)
    # 頂点sから頂点tへの有向辺
    h[t] += 1

root = -1
# 根の頂点番号（出力時の0-indexedから1-indexedへの変換（+1）で0になるようにとる）

q = deque((v1, root) for v1 in range(V) if h[v1] == 0)
# 入次数0の頂点の「番号v1とその親root」

res = [-1] * V
# 親の頂点番号（0-indexedなので、出力時に1-indexedに直す）

while q:
    # qがなくなるまでループ
    v1, root = q.popleft()
    res[v1] = root
    for v2 in g[v1]:
        h[v2] -= 1
        # 隣接する頂点の入次数をマイナス1
        if h[v2] == 0:
            q.append((v2, v1))
            # これによって入次数が0になればqに追加

res = tuple(map(lambda x: x + 1, res))
print(*res, sep='\n')

Submission status: Accepted

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

A = [[] for _ in range(N)]
P = [0]*N
C = [0]*N
root = -1

for (a,b) in AB:
    # a -> b
    A[a-1].append(b-1)
    C[b-1] += 1

for i in range(N):
    if C[i]==0:
        root = i
P[root] = -1

from collections import deque
que = deque((a,root) for a in A[root])
while que:
    n,par = que.popleft()
    C[n] -= 1
    if C[n]==0:
        P[n] = par
        for i in A[n]:
            que.append((i,n))

for p in P:
    print(p+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 全国統一プログラミング王決定戦予選：D - Restore the Tree
import sys
sys.setrecursionlimit(1000000)
back = []


def calc(e):
    global back
    # print 'e =', e, ', b =', back[e]

    if back[e][1] == -1:
        if len(back[e][0]) == 0:
            back[e][1] = 0
            # print 'ret =', 0
            return 0
        elif len(back[e][0]) == 1:
            l = calc(back[e][0][0]) + 1
            back[e][1] = l
            # print 'ret =', l
            return l
        maxl = calc(back[e][0][0])
        maxi = 0
        for i, s in enumerate(back[e][0][1:], 1):
            l = calc(s)
            if l >= maxl:
                maxl = l
                back[e][0][maxi] = -1
                maxi = i
            else:
                back[e][0][i] = -1
        back[e][1] = maxl + 1
        # print 'ret =', maxl + 1
        return maxl + 1
    else:
        # print 'ret =', back[e][1]
        return back[e][1]


def main():
    global back
    N, M = [int(i) for i in raw_input().strip().split(' ')]

    A = []
    for _ in range(N+M-1):
        A.append([int(i)-1 for i in raw_input().strip().split(' ')])
    # H.sort(reverse=False)

    back = [[[], -1] for _ in range(N)]

    for s, e in A:
        back[e][0].append(s)
    # print 'back =', back

    for i, b in enumerate(back):
        if b[1] == -1:
            # back[i][1] = calc(i)
            calc(i)

    # print 'back =', back
    for b in back:
        if b[0] == []:
            print 0
        else:
            for s in b[0]:
                # print 's =', s
                if s != -1:
                    print s+1


if __name__ == '__main__':
    main()

Submission status: Accepted

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

result = [-1] * (N + 1)
edge_from = [[] for _ in range(N + 1)]
edge_to = [[] for _ in range(N + 1)]

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

parent = []
for i in range(1, N + 1):
    if any(edge_to[i]) and not any(edge_from[i]):
        parent.append(i)
        result[i] = 0
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if not any(edge_from[child]):
                result[child] = p
                next_.append(child)
    if not any(next_):
        break
    parent = next_

for x in result[1:]:
    print(x)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import fractions
import heapq
import collections
import re
import array
import bisect
sys.setrecursionlimit(1000000)

from collections import Counter, defaultdict


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))


II = lambda: int(input())
MI = lambda: map(int, input().split())



def main():
    N, M = MI()
    in_edges = [set() for _ in range(N)]
    out_edges = [set() for _ in range(N)]
    num_in_edges = [0] * N
    for _ in range(N - 1 + M):
        a, b = MI()
        a -= 1
        b -= 1
        num_in_edges[b] += 1
        in_edges[b].add(a)
        out_edges[a].add(b)
    Root = argmin(num_in_edges)
    parent = [0] * N
    parent[Root] = -1

    q = [Root]

    while q:
        v = q.pop()
        for child in out_edges[v]:
            in_edges[child].remove(v)
            num_in_edges[child] -= 1
            if num_in_edges[child] == 0:
                parent[child] = v
                q.append(child)

    for p in parent:
        print(p + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

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

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_

for x in result:
    print(x + 1)

Submission status: Accepted

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

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

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

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_.copy()

for x in result:
    print(x + 1)

Submission status: Accepted

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

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

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

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_.copy()

for x in result:
    print(x + 1)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

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

queue = deque(i for i in range(1, N + 1) if in_cnt[i] == 0)
sorted_ans = []

while len(queue) != 0:
    v = queue.popleft()
    sorted_ans.append(v)
    for v2 in out[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [0] + [i + 1 for i, v in sorted(enumerate(sorted_ans), key=lambda x: x[1])]
ans = [0] * (N + 1)
ans[sorted_ans[0] + 1] = 0

for v in sorted_ans[:0:-1]:
    ans[v] = max((order[v2], v2) for v2 in rev[v])[1]
    
for a in ans[1:]:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

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

queue = deque(i for i in range(1, N + 1) if in_cnt[i] == 0)
sorted_ans = []

while len(queue) != 0:
    v = queue.popleft()
    sorted_ans.append(v)
    for v2 in out[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i + 1 for i, v in sorted(enumerate(sorted_ans), key=lambda x: x[1])]
order = [0] + order
ans = [0] * (N + 1)
ans[sorted_ans[0] + 1] = 0

for v in sorted_ans[:0:-1]:
    ans[v] = max((order[v2], v2) for v2 in rev[v])[1]
ans.pop(0)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

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

queue = deque(i for i in range(1, N + 1) if in_cnt[i] == 0)
sorted_ans = []

while len(queue) != 0:
    v = queue.popleft()
    sorted_ans.append(v)
    for v2 in out[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i + 1 for i, v in sorted(enumerate(sorted_ans), key=lambda x: x[1])]
order = [0] + order
ans = [0] * (N + 1)
ans[sorted_ans[sorted_ans[0]] + 1] = 0

for v in sorted_ans[:0:-1]:
    ans[v] = max((order[v2], v2) for v2 in rev[v])[1]
ans.pop(0)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import deque

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

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1

#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            res[e]=z+1
            tank2.append(e)
            usedtank.append(e)

#c : 確定した点の数            
c = 1
tank = deque([root])
tank2 = deque([root])
usedtank = []

while c != n:
    tank = tank2
    tank2 = deque([])
    usedtank = []
    while len(tank)!=0:
        f(tank.popleft())
    for e_used in usedtank:
        used[e_used]=1
    c += len(tank2)
    
for i in range(n):
    print(res[i])

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

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

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1

#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            res[e]=z+1
            tank2.append(e)
            usedtank.append(e)
c = 1
tank = deque([root])
tank2 = deque([root])
usedtank = []
while c != n:
    tank = tank2
    tank2 = deque([])
    usedtank = []
    while len(tank)!=0:
        f(tank.popleft())
    for usede in usedtank:
        used[usede]=1
    c += len(tank2)
    
for i in range(n):
    print(res[i])

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
N,M = map(int,input().split())
es = [[int(x) for x in input().split()] for _ in range(N+M-1)]
ins = defaultdict(int)
outs = defaultdict(list)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
q = deque(v1 for v1 in range(N) if ins[v1]==0)
res = []
ans,c = [0 for i in range(N+1)],0
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2]==0:
            q.append(v2)
            ans[v2]=v1

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

Submission status: Accepted

Solution code:
def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    # count num of pointed nodes for each nodes
    parent = [0]*V
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    while Q:
        del_node = Q.pop()
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)
                parent[j] = del_node+1

    return parent


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

    ans = topological_sort(N, E_in, E_from)
    for s in ans:
        print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n+m-1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

P = [0] * (n+1)
D = [0] * (n+1)

def dfs(i):
    if D[i] > 0:
        return D[i] + 1
    for t in RT[i]:
        d = dfs(t)
        if d > D[i]:
            D[i] = d
            P[i] = t

    return D[i] + 1

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

D[root(1)] = 1

for i in range(1, n+1):
    dfs(i)

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

Submission status: Accepted

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

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n+m-1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

P = [0] * (n+1)
D = [0] * (n+1)

def dfs(i):
    if D[i] > 0:
        return D[i] + 1
    for t in RT[i]:
        d = dfs(t)
        if d > D[i]:
            D[i] = d
            P[i] = t

    return D[i] + 1

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

D[root(1)] = 1

for i, t in enumerate(T):
    if not t:
        dfs(i)

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

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
count = [0] * (N + 1)
ans = [0] * (N + 1)
for a, b in AB:
    G[a].add(b)
    count[b] += 1
for i in range(1, N):
    if count[i] == 0:
        root = collections.deque([i])
        break
while root:
    p = root.popleft()
    for c in G[p]:
        count[c] -= 1
        if count[c] == 0:
            ans[c] = p
            root.append(c)
print(*ans[1:], sep='\n')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2000000)

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

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

for i in range(N-1+M):
  A,B=map(int,input().split())
  child[A-1].append(B-1)
  parent[B-1].append(A-1)
  
for i in range(N):
  if len(parent[i])==0:
    root=i
    break
#print(root)

kazu=[0]*N
for i in range(N):
  kazu[i]=len(parent[i])

answer=[0]*N

def dfs(index):
  search=[]
  for d in child[index]:
    kazu[d]-=1
    if kazu[d]==0:
      search.append(d)
      answer[d]=index+1
  for s in search:
    dfs(s)
    
 
dfs(root)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):

    in_n = [0] * (N+1)
    g = defaultdict(list)
    rg = defaultdict(list)
    for a, b in AB:
        in_n[b] += 1
        g[a].append(b)
        rg[b].append(a)

    r = []
    for i, n in enumerate(in_n):
        if i != 0 and n == 0:
            r.append(i)

    sv = []
    while r:
        u = r.pop()
        sv.append(u)
        for v in g[u]:
            in_n[v] -= 1
            if in_n[v] == 0:
                r.append(v)

    svd = {}
    for i, v in enumerate(sv):
        svd[v] = i
    for i in range(1, N+1):
        mi = 0
        if len(rg[i]) == 0:
            print(0)
        else:
            for j in rg[i]:
                mi = max(mi, svd[j])
            print(sv[mi])
    return


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N+M-1)]
    slv(N, M, AB)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(500000)

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]

for _ in range(N + M - 1):
    u, v = [int(elem) - 1 for elem in fin().split()]
    adj[u].append(v)

inv_adj = [[] for _ in range(N)]
for u, neighbors in enumerate(adj):
    for v in neighbors:
        inv_adj[v].append(u)

topo = []
visited = [False] * N

def dfs_visit(node):
    for neighbor in adj[node]:
        if visited[neighbor]:
            continue
        visited[neighbor] = True
        dfs_visit(neighbor)
    topo.append(node)
    return

for node in range(N):
    if not visited[node]:
        visited[node] = True
        dfs_visit(node)

topo = topo[::-1]

parent = [-1] * N
order = dict()
order[topo[0]] = 0
for number, node in enumerate(topo[1:], start=1):
    neighbors = inv_adj[node]
    correct_parent = -1
    for neighbor in neighbors:
        if neighbor in order and order[neighbor] > correct_parent:
            correct_parent = order[neighbor]
    parent[node] = correct_parent
    order[node] = number

order_to_number = {v: k + 1 for k, v in order.items()}
order_to_number[-1] = 0

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

Submission status: Accepted

Solution code:
from collections import deque

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

n_in = [0] * n
graph = [[] for _ in range(n)]
for i in range(n+m-1):
    A, B = map(int, input().split())
    n_in[B-1] += 1
    graph[A-1].append(B-1)

root = 0
for i in range(n):
    if n_in[i] == 0:
        root = i
        break

parent = [0] * n
q = deque([root])
count = 0
while q:
    node = q.popleft()
    for next_v in graph[node]:
        parent[next_v] = node+1
        n_in[next_v] -= 1
        if n_in[next_v] == 0:
            q.append(next_v)

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

Submission status: Accepted

Solution code:
def topological_sort(V,E_from,E_in):
    IN = [-1]*V
    n = [-1]*V
    for v in range(V):
        IN[v] = len(E_in[v])
        if IN[v] == 0:
            q = [v]
    count = 0
    while q:
        v = q.pop()
        n[v] =  count
        count += 1
        for u in E_from[v]:
            IN[u] -= 1
            if IN[u] == 0:
                q.append(u)
    return n
import heapq
n,m = map(int,input().split())
edge_from = [[] for _ in range(n)]
edge_in = [[] for _ in range(n)]
E = []
for i in range(n+m-1):
    go,to = map(int,input().split())
    go -= 1
    to -= 1
    E.append([go,to])
    edge_from[go].append(to)
    edge_in[to].append(go)
res = topological_sort(n,edge_from,edge_in)
rev = [0]*n
for i in range(n):
    rev[res[i]] = i
reve_from = [[] for _ in range(n)]
reve_in = [[] for _ in range(n)]
for go,to in E:
    resgo = res[go]
    resto = res[to]
    heapq.heappush(reve_from[resgo],-resto)
    heapq.heappush(reve_in[resto],-resgo)
ans = [-1]*n
for i in range(n):
    ans[rev[i]] = rev[-reve_in[i][0]] + 1 if reve_in[i] else 0
for i in ans:
    print(i)