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:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    def dfs(i):
        if c[i]:
            return
        for e in edg[i]:
            dfs(e)
        c[i] = 1
        top.append(i)
    n, m = LI()
    edg = [[] for i in range(n)]
    rev_edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
        rev_edg[b].append(a)
    for i, e in enumerate(rev_edg):
        if len(e):
            continue
        root = i
        break
    c = defaultdict(int)
    top = []
    dfs(root)
    ind = [0] * n
    for i in range(n):
        ind[top[i]] = i
    ans = [-1] * n
    for i in range(n):
        tmp = [n, -1]
        for e in rev_edg[i]:
            if ind[e] < tmp[0]:
                tmp = [ind[e], e]
        ans[i] = tmp[1]
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

# restore the tree


from collections import deque
n, m = map(int, input().split())


in_node = [0 for i in range(n + 1)]

# in_node[x]=xに入るノードの数

parent_node = [0 for i in range(n + 1)]

# parent[i]=ねつき木における頂点iの親を返す

in_graph = {i: [] for i in range(1, n + 1)}

out_graph = {i: [] for i in range(1, n + 1)}

# graph[i]=頂点iに入るノードの集合リスト

# out_graph[i]=頂点iから出るノードの集合リスト

for _ in range(n + m - 1):
    a, b = map(int, input().split())
    in_graph[b].append(a)
    out_graph[a].append(b)
    in_node[b] += 1

root = -1


for i in range(1, n + 1):
    if in_node[i] == 0:
        parent = i
        break



flag = True
d = deque()
d.append(parent)
while d:
    x = d.popleft()
    not_yet = False
    for node in out_graph[x]:
        in_node[node] -= 1
        if in_node[node] == 0 and parent_node[node] == 0:
            parent_node[node] = x
            d.append(node)
            not_yet = True

    if not_yet:
        flag = True
    else:
        flag = False

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

Submission status: Accepted

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


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}
    e = {i:[] for i in range(1, N+1)}
    h = [0] * (N+1)

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

    st = set()
    for i in range(1, N+1):
        if h[i]==0:
            st.add(i)

    tp = {}
    c = 0
    while st:
        i = st.pop()
        c += 1
        tp[i] = c
        for j in d[i]:
            h[j] -= 1
            if h[j] == 0:
                st.add(j)

    ans = [0] * (N+1)
    for i in range(1, N+1):
        s, t = 0, 0
        for j in e[i]:
            if s < tp[j]:
                s = tp[j]
                t = j
        print(t)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
e = {i:[] for i in range(1, N+1)}

l = []
h = [0] * (N+1)

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

st = set()
for i in range(1, N+1):
    if h[i]==0:
        st.add(i)

l = []
while st:
    i = st.pop()
    l.append(i)
    for j in d[i]:
        h[j] -= 1
        if h[j] == 0:
            st.add(j)

tp = {j:i for i,j in enumerate(l, start=1)}
ans = [0] * (N+1)
for i in range(1, N+1):
    s, t = 0, 0
    for j in e[i]:
        if s < tp[j]:
            s = tp[j]
            t = j
    print(t)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.dafaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる
N,M = m()
po = [0 for i in range(N)]
num = [-1 for i in range(N)]
g = cl.defaultdict(set)
gg = cl.defaultdict(set)
for i in range(N-1+M):
    s,t = m()
    g[s-1] |= {t-1}
    gg[t-1] |= {s-1}
a = list(Topo_sort(g,N))


for i in range(N):
    ppp = a[i]
    num[ppp] = i
    if i != 0:
        dp = -1
        for nu in gg[ppp]:
            if num[nu] > dp:
                dp = num[nu]
                po[ppp] = nu+1

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

Submission status: Accepted

Solution code:
import heapq as h
import sys

input=sys.stdin.readline


N,M=map(int,input().split())
to=[set([]) for i in range(0,N)]
fr=[set([]) for i in range(0,N)]
for i in range(0,N+M-1):
    a,b=map(int,input().split())
    to[a-1].add(b-1)
    fr[b-1].add(a-1)

root=-1
for i in range(0,N):
    if fr[i]==set([]):
        root=i
        break

parent=[-1 for i in range(0,N)]
visited=set([])
q=[]
q.append(root)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        visited.add(x)
        for p in to[x]:
            if visited>=fr[p]:
                h.heappush(sub,p)
                parent[p]=x
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

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

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
from collections import defaultdict

inc=[0]*n
out=defaultdict(list)
link = [[] for _ in range(n)]
for i in range(n-1+m):
    a,b = list(map(int,input().split()))
    a-=1
    b-=1
    inc[b]+=1
    out[a].append(b)
    link[a].append(b)

s=[]
for i in range(len(inc)):
    if inc[i]==0:
        s.append(i)

res=[]
ans=[-1]*n
ans[s[0]]=0

while s:
    n=s.pop()
    res.append(n)
    for m in out[n]:
        inc[m]-=1
        if inc[m]==0:
            ans[m]=n+1
            s.append(m)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


# トポロジカルソート
# deg[i] := 頂点iの入次数
# returns := トポロジカルソートされた頂点番号のリスト
def tsort(deg, nl):
    tsorted = list()
    stack = [i for i, x in enumerate(deg) if x == 0]
    while len(stack) > 0:
        v = stack.pop()
        tsorted.append(v)
        for next_v in nl[v]:
            deg[next_v] -= 1
            if deg[next_v] == 0:
                stack.append(next_v)
    return tsorted


N, M = MI()

nl = [list() for _ in range(N)]
deg = [0 for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = MI()
    A, B = A - 1, B - 1
    nl[A].append(B)
    deg[B] += 1

tsorted = tsort(deg, nl)

ans = [0] * N
p = {tsorted[0]: -1}
for v in tsorted:
    ans[v] = p[v]
    for next_v in nl[v]:
        p[next_v] = v
for a in ans:
    print(a + 1)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()

nl = [list() for _ in range(N + 1)]
rev = [list() for _ in range(N + 1)]
deg = [0 for _ in range(N + 1)]
for _ in range(N - 1 + M):
    A, B = MI()
    nl[A].append(B)
    rev[B].append(A)
    deg[B] += 1

for i, l in enumerate(deg):
    if i > 0 and l == 0:
        root = i
        break

stack = [root]
tsorted = list()
while len(stack) > 0:
    v = stack.pop()
    tsorted.append(v)
    for next_v in nl[v]:
        deg[next_v] -= 1
        if deg[next_v] == 0:
            stack.append(next_v)

ans = [0] * (N + 1)
p = {root: 0}
for v in tsorted:
    ans[v] = p[v]
    for next_v in nl[v]:
        p[next_v] = v
for a in ans[1:]:
    print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)
IN = [0] * (n+1)
P = [0] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])
    IN[C[i][1]] += 1

# INはその頂点を指している辺の本数のリスト

S = []
s = 0

for i in range(n):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        if IN[x] == 0:
            S.append(x)
    s += 1

for i in S:
    for j in M[i]:
        P[j] = i
for i in range(1, n+1):
    print(P[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)

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

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])
    F[C[i][1]] += 1

# 1始まりの場合
Q = [r]
s = 0
# V[r] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        F[x] -= 1
        if F[x] == 0:
            P[x] = i
            Q.append(x)
    s += 1
# print(P)

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
V = n
from collections import defaultdict
g = defaultdict(list)
deg = defaultdict(int)

abl = []
for _ in range(n+m-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    deg[b-1] += 1
    abl.append((a,b))

# V: 頂点数
# G[v] = [w, ...]:
#    有向グラフ上の頂点vから到達できる頂点w
# deg[v]:
#    頂点vに到達できる頂点の数

from collections import deque
ans = list(v for v in range(V) if deg[v]==0)
deq = deque(ans)
used = [0]*V

while deq:
    v = deq.popleft()
    for t in g[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)

dic = defaultdict(int)
for idx, a in enumerate(ans):
    dic[a] = idx

headl = [-1 for i in range(n)]
for a,b in abl:
    if headl[b-1] == -1:
        headl[b-1] = a-1
    else:
        if dic[headl[b-1]] < dic[a-1]:
            headl[b-1] = a-1

for i in headl:
    print(i+1)

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
data=[[] for i in range(N+1)]
lst=set()
came=[set() for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    lst.add(b)
    came[b].add(a)

st=list(set(range(1,N))-lst)[0]
stack=deque([st])
lst=[0 for i in range(N+1)]


while stack:
    a=stack.popleft()
    for p in data[a]:
        came[p].remove(a)
        if not came[p]:
            lst[p]=a
            stack.append(p)

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

Submission status: Accepted

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

N, M = map(int, input().split())
is_root = [False] + [True] * N
par_count = [0] * (N+1)
G = [[] for _ in range(N+1)]
for _ in range(N-1+M):
    A, B = map(int, input().split())
    G[A].append(B)
    par_count[B] += 1
    is_root[B] = False
root = is_root.index(True)
queue = deque()
queue.append(root)
parent = [0] * (N+1)
while queue:
    u = queue.popleft()
    for v in G[u]:
        if par_count[v] > 1:
            par_count[v] -= 1
        else:
            parent[v] = u
            queue.append(v)
for i in range(1, N+1):
    print(parent[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, m = LI()
G = [set() for _ in range(n)]
RG = [set() for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = LI()
    G[a - 1].add(b - 1)
    RG[b - 1].add(a - 1)

r = 0
while RG[r]:
    for v in RG[r]:
        r = v
        break

def topological_sort():
    in_degree = [0] * n
    D = {}
    for u in range(n):
        in_degree[u] += len(RG[u])
    dq = deque([r])
    cnt = 0
    while dq:
        u = dq.pop()
        D[u] = cnt
        cnt += 1
        for v in G[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                dq += [v]
    return D

D = topological_sort()
for u in range(n):
    par = 0
    ret = -1
    for v in RG[u]:
        if D[v] > ret:
            ret = D[v]
            par = v + 1
    print(par)

Submission status: Accepted

Solution code:
from collections import deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = [[] for i in range(N+1)]
  par =  ['0']*N
  cnt = [0]*(N+1)
  cnt[0] = 1
  for a,b in zip(*[iter(L)]*2):
    dic[a].append(b)
    cnt[b] += 1

  for i, m in enumerate(cnt):
    if m==0:
      q = deque([i])
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q.append(c)

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
#書き足された各辺 u→v は、
#ある頂点 uからその子孫であるような
#頂点vに向かって伸びています。
#bfsでよい
from sys import stdin
from collections import deque
input = stdin.readline
n,m = map(int, input().split( ))

E = [[] for _ in range(n)]

P = [-1]*n
deg = [0]*n
for i in range(n+m-1):
    ai,bi = map(int, input().split( ))
    ai-=1;bi-=1
    E[ai].append(bi)
    deg[bi]+=1
r = deg.index(0)

Q = deque()
Q.append(r)
P[r] = r

while Q:
    v = Q.popleft()
    for u in E[v]:
        if deg[u]==1:
            P[u]=v
            deg[u]-=1
            Q.append(u)
        else:
            deg[u]-=1


for i in range(n):
    if P[i]==i:
        print(0)
    else:
        print(P[i]+1)

Submission status: Accepted

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
cnt=[0]*(n+1)
for _ in range((n-1)+m):
  a,b=map(int,input().split())
  g[a].append(b)
  cnt[b]+=1
root=0
for i in range(1,n+1):
  if cnt[i]==0:
    root=i
    break
ans=[0]*(n+1)
q=collections.deque()
q.append(root)
while len(q)!=0:
  v=q.popleft()
  for u in g[v]:
    if cnt[u]==1:
      ans[u]=v
      q.append(u)
    else:
      cnt[u]-=1
for i in range(1,n+1):
  print(ans[i])

Submission status: Accepted

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

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

    for x,num in enumerate(pcount):
        if num == 0:
            root = x
            
    ans = [None for _ in range(N)]
    ans[root] = 0
    q = deque([root])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            pcount[fol] -= 1
            if pcount[fol] == 0:
                ans[fol] = now+1
                q.append(fol)
    
    print(*ans,sep="\n")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from collections import deque
n,m = inm()
chi = [{} for i in range(n+1)]
par = [{} for i in range(n+1)]
for i in range(n-1+m):
    a,b = inm()
    chi[a][b] = 1
    par[b][a] = 1
dep = [0]*(n+1)
rpar = [0]*(n+1)
for i in range(1,n+1):
    if len(par[i])==0:
        root = i
        break
ddprint("chi")
ddprint(chi)
ddprint("par")
ddprint(par)
ddprint(root)
q = deque([root])
while len(q)>0:
    p = q.popleft()
    d = dep[p]
    for z in chi[p]:
        del par[z][p]
        #if dep[z]<d+1 and len(par[z])==0:
        if len(par[z])==0:
            dep[z] = d+1
            rpar[z] = p
            q.append(z)
for i in range(1,n+1):
    print(rpar[i])

Submission status: Accepted

Solution code:
#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
precnt = [0 for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  precnt[b] += 1
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [-1 for _ in range(n)]
now = [r]
#print(precnt)
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      precnt[y] -= 1
      if precnt[y] == 0:
        now.append(y)
      pre[y] = x
#print(pre)
#print(precnt)
for x in pre:
  print(x+1)

Submission status: Accepted

Solution code:
from collections import deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = [[] for i in range(N+1)]
  par =  [None]*N
  cnt = [0]*(N+1)
  cnt[0] = 1
  for a,b in zip(*[iter(L)]*2):
    dic[a].append(b)
    cnt[b] += 1

  for i, m in enumerate(cnt):
    if m==0:
      q = deque([i])
      par[i-1] = 0
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = m
        q.append(c)

  ans = '\n'.join(map(str,par))
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
# どこから来たのかを記録
come_from = [set() for _ in range(N+1)]
edges = [set() for _ in range(N+1)]
for _ in range(N-1+M):
    a, b = lr()
    come_from[b].add(a)
    edges[a].add(b)

from_num = [len(x) for x in come_from]
root = 0
for i in range(1, N+M):
    if from_num[i] == 0:
        root = i
        break

parent = [-1] * (N+1)
parent[root] = 0
stack = [root]
while stack:
    x = stack.pop()
    for y in edges[x]:
        if len(come_from[y]) > 1:
            come_from[y].remove(x)
            continue
        parent[y] = x
        stack.append(y)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    deg = [0]*N
    for _ in range(N-1+M):
        a, b = (int(i)-1 for i in input().split())
        edge[a].append(b)
        deg[b] += 1  # 入次数
    from collections import deque
    que = deque()

    ans = []
    for i in range(N):
        if deg[i] == 0:
            que.append(i)  # root
            ans.append((i, 0))
    # print(que)
    while que:
        u = que.popleft()
        # print(u, ":", edge[u])
        for v in edge[u]:
            deg[v] -= 1
            if deg[v] == 0:
                que.append(v)
                ans.append((v, u + 1))
    ans.sort()
    ans = [p[1] for p in ans]
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# E[i]: 頂点iから伸びる頂点の集合
E = [[] for _ in range(N)]
# parent_cnt[i]: 頂点iの親
parent_cnt = [0] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    parent_cnt[B-1] += 1

# 根を見つける
for i,num in enumerate(parent_cnt):
    if num == 0:
        root = i
        break

parent = [None] * N
parent[root] = 0

q = [root]
# BFS O(N+M)
while q:
    qq = []
    for V in q:
        for Vto in E[V]:
            parent_cnt[Vto] -= 1

            # 親が決定
            if parent_cnt[Vto] == 0:
                parent[Vto] = V + 1
                qq.append(Vto)
    
    q = qq

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

Submission status: Accepted

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

# E[i]: 頂点iから伸びる頂点の集合
E = [[] for _ in range(N)]
# parent_cnt[i]: 頂点iの親
parent_cnt = [0] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    parent_cnt[B-1] += 1

# 根を見つける
for i,num in enumerate(parent_cnt):
    if num == 0:
        root = i
        break

parent = [None] * N
parent[root] = 0

q = [root]
# DFS O(N+M)
while q:
    qq = []
    for V in q:
        for Vto in E[V]:
            parent_cnt[Vto] -= 1

            # 親が決定
            if parent_cnt[Vto] == 0:
                parent[Vto] = V + 1
                qq.append(Vto)
    
    q = qq

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

Submission status: Accepted

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

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

from collections import deque
rnk = [-1]*N
q = deque([root])
rnk[root] = 0
while q:
    temp = q.popleft()
    for v in chl[temp]:
        if rnk[v] < 0:
            rnk[v] = rnk[temp]+1
            q.append(v)

ans = [-1]*N
ans[root] = 0
q = deque([root])
while q:
    temp = q.popleft()
    for v in chl[temp]:
        if len(par[v]) == 1:
            ans[v] = temp+1
            q.append(v)
        else:
            par[v].remove(temp)

for a in ans:
    print(a)

Submission status: Accepted

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

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


# 1. 入次数が0のやつが親
# 2. 親が決まれば、そのこの入次数を減らす,1に戻る

# 親を決めるよ
for i, e in enumerate(e_in[1:], start=1):
    if len(e) == 0:
        root = i
        break

node = [root]
parent = [-1] * (N + 1)
parent[root] = 0
diff = [0] * (N + 1)  # 入次数をどれだけ減らすか

while node:
    s = node.pop()
    for t in e_out[s]:
        diff[t] += 1
        if len(e_in[t]) - diff[t] == 0:
            parent[t] = s
            node.append(t)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [None]*N
  cnt = [0]*(N+1)
  cnt[0] = 1
  for a,b in zip(*[iter(L)]*2):
    dic[a].append(b)
    cnt[b] += 1

  for i, m in enumerate(cnt):
    if m==0:
      q = deque([i])
      par[i-1] = 0
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = m
        q.append(c)

  ans = '\n'.join(map(str,par))
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [None]*N
  cnt = [0]*(N+1)
  cnt[0] = 1
  for a,b in zip(*[iter(L)]*2):
    dic[a].append(b)
    cnt[b] += 1

  for i, m in enumerate(cnt):
    if m==0:
      q = deque([i])
      par[i-1] = '0'
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q.append(c)

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [None]*N
  cnt = [0]*(N+1)
  for a,b in zip(*[iter(L)]*2):
    dic[a].append(b)
    cnt[b] += 1

  for i in range(1,N+1):
    if cnt[i]==0:
      q = deque([i])
      par[i-1] = '0'
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q.append(c)

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [None]*N
  cnt = [0]*(N+1)
  for a,b in zip(*[iter(L)]*2):
    dic[a] += [b]
    cnt[b] += 1

  for i in range(1,N+1):
    if cnt[i]==0:
      q = deque([i])
      par[i-1] = '0'
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q.append(c)

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [None]*N
  cnt = [0]*(N+1)
  for a,b in zip(*[iter(L)]*2):
    dic[a] += [b]
    cnt[b] += 1

  for i in range(1,N+1):
    if cnt[i]==0:
      q = [i]
      par[i-1] = '0'
      break
  
  while q:
    m = q.pop()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q += [c]

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [None]*N
  cnt = [0]*(N+1)
  for a,b in zip(*[iter(L)]*2):
    dic[a] += [b]
    cnt[b] += 1

  for i in range(1,N+1):
    if cnt[i]==0:
      q = deque([i])
      par[i-1] = '0'
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q += [c]

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [0]*N
  cnt = [0]*N
  for a,b in zip(*[iter(L)]*2):
    dic[a-1] += [b-1]
    cnt[b-1] += 1

  for i in range(N):
    if cnt[i]==0:
      q = deque([i])
      par[i] = '0'
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c] = str(m+1)
        q += [c]

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [0]*N
  cnt = [0]*N
  for a,b in zip(*[iter(L)]*2):
    dic[a-1] += [b-1]
    cnt[b-1] += 1

  for i in range(N):
    if not cnt[i]:
      q = deque([i])
      par[i] = '0'
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if not cnt[c]:
        par[c] = str(m+1)
        q += [c]

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = defaultdict(list)
  par =  [0]*N
  cnt = [0]*(N+1)
  for a,b in zip(*[iter(L)]*2):
    dic[a] += [b]
    cnt[b] += 1

  for i in range(1,N+1):
    if cnt[i]==0:
      q = deque([i])
      par[i-1] = '0'
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q += [c]

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()