[백준][그래프] 11725.트리의 부모 찾기

11725.트리의 부모 찾기

 

 

• 내 풀이
  • union-find로 풀려고함
  • 근데 뒤에서 바뀌는 부모를 처리못해서 fail

 

• 풀이
  • bfs로 루트 1부터 시작해서 자식노드에 해당 부모를 순서대로 넣어주면 되는 간단한 문제였다..!

from collections import deque,defaultdict

n=int(input())
parents=[i for i in range(n+1)]
graph=defaultdict(list)
for _ in range(n-1):
    a,b=map(int,input().split())

    graph[a].append(b)
    graph[b].append(a)

def bfs():
    queue=deque([1])
    visited=[False for _ in range(n+1)]
    visited[1]=True

    while queue:
        cur=queue.popleft()
        for nxt in graph[cur]:
            if visited[nxt]:
                continue
            visited[nxt]=True
            parents[nxt]=cur
            queue.append(nxt)

bfs()
for i in range(2,n+1):
    print(parents[i])