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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




def topological_sort(graph):
  N = len(graph)
  in_cnt = [0 for i in range(N)]
  for x in range(N):
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in range(N) if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in range(N) if in_cnt[i]]:
    return None
  return ret

N,M = IL()
graph = [set() for i in range(N)]
graph_from = [set() for i in range(N)]

for i in range(N+M-1):
  a,b = IL()
  graph[a-1].add(b-1)
  graph_from[b-1].add(a-1)
  
dic2 = topological_sort(graph)

dic = [None]*N
for i in range(N):
  dic[dic2[i]] = i

ans = []
for y in range(N):
  d = -1
  p = 0
  for x in graph_from[y]:
    if dic[x] > d:
      d = dic[x]
      p = x+1
  ans.append(p)

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




def topological_sort(graph_to, graph_from):
  graph_from_cnt = [len(graph_from[i]) for i in range(N)]
  dic = DD(int)
  q = deque([i for i in range(N) if not graph_from_cnt[i]])
  while q:
    x = q.popleft()
    dic[x] = len(dic)
    for y in graph_to[x]:
      graph_from_cnt[y] -= 1
      if not graph_from_cnt[y]:
        q.append(y)
  return dic

N,M = IL()
graph_to = [set() for i in range(N)]
graph_from = [set() for i in range(N)]
graph_from_cnt = [0 for i in range(N)]

for i in range(N+M-1):
  a,b = IL()
  graph_to[a-1].add(b-1)
  graph_from[b-1].add(a-1)

dic = topological_sort(graph_to, graph_from)

ans = []
for y in range(N):
  d = -1
  p = 0
  for x in graph_from[y]:
    if dic[x] > d:
      d = dic[x]
      p = x+1
  ans.append(p)

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()
graph_to = [set() for i in range(N)]
graph_from = [set() for i in range(N)]
graph_from_cnt = [0 for i in range(N)]

for i in range(N+M-1):
  a,b = IL()
  graph_to[a-1].add(b-1)
  graph_from[b-1].add(a-1)
  graph_from_cnt[b-1] += 1
for i in range(N):
  if not graph_from[i]:
    root = i

dic = DD(int)
q = deque([root])
while q:
  x = q.popleft()
  dic[x] = len(dic)
  for y in graph_to[x]:
    graph_from_cnt[y] -= 1
    if not graph_from_cnt[y]:
      q.append(y)

ans = []
for y in range(N):
  d = -1
  p = 0
  for x in graph_from[y]:
    if dic[x] > d:
      d = dic[x]
      p = x+1
  ans.append(p)

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

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union








from collections import deque                






















def main():
    Num = Union[int, float]
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    
    
    
    n, m = mi()
    adj = [[] for _ in range(n)]
    rev_adj = [[] for _ in range(n)]
    for _ in range(n + m - 1):
        a, b = mi_0()
        adj[a].append(b)
        rev_adj[b].append(a)
    
    dimention = [len(rev_adj[i]) for i in range(n)]
    parent = [-1] * n
    root = dimention.index(0)

    
    
    
    

    def bfs(start):
        q = deque()
        q.append((start, -1))
        while q:
            u, prev = q.popleft()
            parent[u] = prev
            for v in adj[u]:
                if dimention[v] == 1:
                    q.append((v, u))
                else:
                    dimention[v] -= 1

    bfs(root)

    
    

    for p in parent:
        print(p + 1)



if __name__ == "__main__":
    main()

Solution (Python):
import collections
N, M, *AB = [int(_) for _ in open(0).read().split()]
parent_children = collections.defaultdict(set)
child_parents = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    parent_children[a].add(b)
    child_parents[b].add(a)
root = (set(range(1, N + 1)) - set(child_parents.keys())).pop()


def bfs(root):
    Q = collections.deque([root])
    while Q:
        cur = Q.pop()
        for to in parent_children[cur]:
            if len(child_parents[to]) > 1:
                child_parents[to].remove(cur)
            else:
                Q += [to]


bfs(root)
child_parents[root] = {0}
for i in range(1, N + 1):
    print(child_parents[i].pop())

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
parents = [-1]*N
query = [[] for _ in range(N)]
get_into = [0]*N
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    get_into[b-1] += 1
    query[a-1].append(b-1)

for i, c in enumerate(parents):
    if c==-1:
        root = i
        break

from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        get_into[nx] -= 1
        if get_into[nx]==0:
            parents[nx] = v
            Q.append(nx)

for p in parents:
    print(p+1)

Solution (Python):
def main():
    import networkx as nx
    import sys
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for i in range(N-1+M)]
    DG = nx.DiGraph(AB)

    G = [set() for i in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        G[a].add(b)

    DG = list(nx.topological_sort(DG))

    parent = [0]*N
    for i, x in enumerate(DG):
        x -= 1
        if i == 0:
            parent[x] = 0
        for y in G[x]:
            parent[y] = x+1
    print(*parent, sep='\n')


main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
ALL = [i for i in range(N)]
ALL = set(ALL)
Graph = [[] for _ in range(N)]
gyaku = [set([]) for _ in range(N)]
for i in range(N-1+M):
  a,b = map(int,input().split())
  a-=1;b-=1
  Graph[a].append(b)
  gyaku[b].add(a)
  ALL.discard(b)

ALL = list(ALL);root = ALL[0]

used = set([])
TS = []
def dfs(v):
  if v in used:
    return
  used.add(v)
  for w in Graph[v]:
    if w in used:
      continue
    dfs(w)
    TS.append(w)
    
dfs(root)
TS.append(root)
TS.reverse()

ans = [0 for _ in range(N)]
for i in range(N):
  now = TS[i]
  for nxt in Graph[now]:
    ans[nxt] = now+1
    
for x in ans:
  print(x)

Solution (Python):
from collections import deque
N,M = map(int, input().split())
E = [[] for _ in range(N)]
memo = [0]*N
for _ in range(N+M-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    memo[b-1] += 1

root = memo.index(0)
rnk = [0]*N
par = [-1]*N

q = deque()
q.append(root)
while q:
    temp = q.popleft()
    u = temp%N
    r = temp//N
    for v in E[u]:
        memo[v] -= 1
        if memo[v] > 0:
            continue
        rnk[v] = r+1
        par[v] = u
        q.append((r+1)*N+v)

for p in par:
    print(p+1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
root_kouho=set(list(range(n)))
leaf=set(list(range(n)))
ki=[[] for _ in range(n)]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  root_kouho.discard(b)
  leaf.discard(a)
  ki[b].append(a)
root=root_kouho.pop()
ans=[-1]*n
dp=[-1]*n 
ans[root]=0
dp[root]=0
def func(v):
  if dp[v]>=0:
    return dp[v]
  else:
    ret=-1
    for nv in ki[v]:
      tmp=func(nv)
      if ret<tmp:
        ret=tmp
        ans[v]=nv+1
    dp[v]=ret+1
    return ret+1
while leaf:
  l=leaf.pop()
  func(l)
print(*ans,sep='\n')

Solution (Python):
import sys
input = sys.stdin.buffer.readline


class DiGraph:
    def __init__(self, n, decrement=True, destroy=False, edges=[]):
        """
        incs[p]: 頂点 p に流入するリンク数
        """
        self.n = n
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.incs = [0]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.incs[y] += 1

    def topological_sort(self):
        next_set = {p for p, inc in enumerate(self.incs) if inc == 0}
        res = []
        while next_set:
            p = next_set.pop()
            res.append(p+self.decrement)
            for q in self.edges[p]:
                self.incs[q] -= 1
                if self.incs[q] == 0:
                    next_set.add(q)
        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.DiGraph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()




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

    M = N - 1 + M
    graph = DiGraph(N, decrement=True, destroy=True)
    for _ in range(M):
        A, B = map(int, input().split())
        graph.add_edge(A, B)

    res = [0]*N
    for p in graph.topological_sort():
        for q in graph.edges[p-1]:
            res[q] = p
    print(*res, sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline


class DiGraph:
    def __init__(self, n, decrement=True, destroy=False, edges=[]):
        """
        incs[p]: 頂点 p に流入するリンク数
        """
        self.n = n
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.incs = [0]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.incs[y] += 1

    def topological_sort(self):
        next_set = {p for p, inc in enumerate(self.incs) if inc == 0}
        while next_set:
            p = next_set.pop()
            yield p+self.decrement
            for q in self.edges[p]:
                self.incs[q] -= 1
                if self.incs[q] == 0:
                    next_set.add(q)

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.DiGraph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()




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

    M = N - 1 + M
    graph = DiGraph(N, decrement=True, destroy=False)
    for _ in range(M):
        A, B = map(int, input().split())
        graph.add_edge(A, B)

    res = [0]*N
    for p in graph.topological_sort():
        for q in graph.edges[p-1]:
            res[q] = p
    print(*res, sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):




import sys
input = sys.stdin.buffer.readline


class DiGraph:
    def __init__(self, n, decrement=True, destroy=False, edges=[]):
        """
        incs[p]: 頂点 p に流入するリンク数
        """
        self.n = n
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.incs = [0]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.incs[y] += 1

    def topological_sort(self):
        next_set = {p for p, inc in enumerate(self.incs) if inc == 0}
        while next_set:
            p = next_set.pop()
            yield p+self.decrement
            for q in self.edges[p]:
                self.incs[q] -= 1
                if self.incs[q] == 0:
                    next_set.add(q)

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.DiGraph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()




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

    M = N - 1 + M
    graph = DiGraph(N, decrement=True, destroy=True)
    for _ in range(M):
        A, B = map(int, input().split())
        graph.add_edge(A, B)

    res = [0]*N
    for p in graph.topological_sort():
        for q in graph.edges[p-1]:
            res[q] = p
    print(*res, sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):




import sys
input = sys.stdin.buffer.readline


class DiGraph:
    def __init__(self, n, decrement=True, destroy=False, edges=[]):
        """
        incs[p]: 頂点 p に流入するリンク数
        """
        self.n = n
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.incs = [0]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.incs[y] += 1

    def topological_sort(self):
        next_set = {p for p, inc in enumerate(self.incs) if inc == 0}
        res = []
        while next_set:
            p = next_set.pop()
            res.append(p+self.decrement)
            for q in self.edges[p]:
                self.incs[q] -= 1
                if self.incs[q] == 0:
                    next_set.add(q)
        if len(res) == self.n:
            return res
        else:
            return -1

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.DiGraph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()




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

    M = N - 1 + M
    graph = DiGraph(N, decrement=True, destroy=False)
    for _ in range(M):
        A, B = map(int, input().split())
        graph.add_edge(A, B)

    temp = graph.topological_sort()
    res = [0]*N
    for p in temp:
        for q in graph.edges[p-1]:
            res[q] = p
    print(*res, sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):




import sys
input = sys.stdin.readline


class DiGraph:
    def __init__(self, n, decrement=True, destroy=False, edges=[]):
        """
        incs[p]: 頂点 p に流入するリンク数
        """
        self.n = n
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.incs = [0]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.incs[y] += 1

    def topological_sort(self):
        next_set = {p for p, inc in enumerate(self.incs) if inc == 0}
        res = []
        while next_set:
            p = next_set.pop()
            res.append(p+self.decrement)
            for q in self.edges[p]:
                self.incs[q] -= 1
                if self.incs[q] == 0:
                    next_set.add(q)
        if len(res) == self.n:
            return res
        else:
            return -1

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.DiGraph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()




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

M = N - 1 + M
graph = DiGraph(N, decrement=True, destroy=False)
rev = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    graph.add_edge(A, B)

temp = graph.topological_sort()
res = [0]*N
for p in temp:
    for q in graph.edges[p-1]:
        res[q] = p
print(*res, sep="\n")

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque,defaultdict

n,m = map(int,readline().split())
c = [set() for i in range(n)]
d = defaultdict(int)
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  c[a].add(b)
  d[b] += 1
  
ans = [0]*n
root = deque()
for i in range(n):
  if d[i] == 0:
    root.append(i)
    break
cnt = 1

while True:
  now = root.popleft()
  for nex in c[now]:
    d[nex] -= 1
    if d[nex] == 0:
      cnt += 1
      ans[nex] = now+1
      root.append(nex)
  if cnt == n:
    break
print(*ans,sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    """
    書き足した辺は，子孫に対してのものなのでいわゆるショートかっと．
    後から同じ頂点にたどり着いた場合，そちらを優先する？

    """
    
    mod=10**9+7
    N,M=MI()
    fro=[[]for _ in range(N)]
    to=[[]for _ in range(N)]
    
    for _ in range(N+M-1):
        a,b=MI()
        a-=1
        b-=1
        fro[b].append(a)
        to[a].append(b)
        
    root=0
    target=[0]*N
    for i in range(N):
        target[i]=len(fro[i])
        if target[i]==0:
            root=i
        
    P=[-1]*N
    
    
    count=[0]*N
    
    import queue
    q=queue.Queue()
    q.put(root)
    
    while not q.empty():
        v=q.get()
        for nv in to[v]:
            count[nv]+=1
            if count[nv]==target[nv]:
                q.put(nv)
                P[nv]=v
                
    for i in range(N):
        print(P[i]+1)
    
        

main()

Solution (Python):
"""
子孫に向かって有向辺が伸びる
⇨ ループなし
⇨ トポロジカルソート通りに並べると親がわかる
"""
from collections import deque
from collections import defaultdict
n, m = map(int, input().split())

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

def topo(G):
    cut_in = defaultdict(int)
    for vs in G:
        for v in vs:
            cut_in[v] += 1
    res = []
    
    zeros = [i for i in range(n) if cut_in[i] == 0]
    q = deque(zeros)
    
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for u in G[v]:
            cut_in[u] -= 1
            if cut_in[u] == 0:
                q.append(u)
    return res

ss = topo(edges)

ss = {s:i for i,s in enumerate(ss)}

for i in range(n):
    mn = -1
    parent = 0
    if len(ps[i]) == 0:
        print(0)
        continue
    for p in ps[i]:
        if mn < ss[p]:
            mn = ss[p]   
            parent = p
    print(parent+1)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*n
dic=defaultdict(list)
for a,b in ab:
    dic[a-1].append(b-1)
    lst[b-1]+=1

ne=-1
for i in range(n):
    if lst[i]==0:
        ne=i

g=[-1]*n
d=deque([ne])
while d:
    now=d.popleft()
    for i in dic[now]:
        lst[i]-=1
        if lst[i]==0:
            d.append(i)
            g[i]=now


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

Solution (Python):
from collections import deque
n,m = map(int,input().split())
e = [[] for i in range(n)]
d = [1]*n
s = [0]*n
t = [[] for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    t[b].append(a)
    s[b] += 1


ans = [-1]*n
p = s.index(0)
ans[p] = 0
q = deque([])
q.append(p)
s = set()

while q:
    now = q.popleft()
    s.add(now)
    for nex in e[now]:
        if ans[nex] == -1:
            check = True
            for j in t[nex]:
                if j not in s:
                    check = False
                    break
            if check:
                ans[nex] = now+1
                q.append(nex)
for i in ans:
    print(i)