백준 11725 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.www.acmicpc.net

1을 시작으로 dfs든 bfs든 하면서 parent를 업데이트해준다.

#dfs

import syssys.setrecursionlimit(10**6)input=sys.stdin.readlinedef dfs(node=1):
    for next_node in arr[node]:        if parent[next_node]==-1:
            parent[next_node]=node            dfs(next_node)n=int(input())
parent=[-1 for _ in range(n+1)]arr=[[]for _ in range(n+1)]for _ in range(n-1):
    a,b=map(int,input().split())    arr[a].append(b)    arr[b].append(a)dfs()
for p in parent[2:]:    print(p)

#bfs

import sysfrom collections import dequeinput=sys.stdin.readlinedef bfs(root=1):
    que=deque([root])        while que:        node=que.popleft()
        for next_node in arr[node]:            if parent[next_node]==-1:
                parent[next_node]=node                que.append(next_node)    
n=int(input())parent=[-1 for _ in range(n+1)]arr=[[]for _ in range(n+1)]
for _ in range(n-1):    a,b=map(int,input().split())    arr[a].append(b)
    arr[b].append(a)bfs()for p in parent[2:]:    print(p)