11725_트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

 

트리란 그래프의 일종인데, 중복된 곳에서 한 점으로 올 수 없는 구조이다.

 

 

 

해당 문제에서 트리구조를 찾기위해선, 먼저 연결관계를 모두 기록한 후에 1번 노드를 첫번째 부모로 둔 후, 자식들을 연결해 나가면 해결할 수 있다.

 

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

n = int(input())
tree = [ [] for _ in range(n + 1)]
parents =[ 0 for _ in range(n + 1)]

for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

def dfs(node):
    for i in tree[node]:
        if parents[i] == 0:
            parents[i] = node
            dfs(i)
dfs(1)


print(*parents[2:],sep='\n')

이때 문제해결을 위해 재귀함수 제한을 풀어줘야 백준이 통과된다!