[백준] 11725번 트리의 부모 찾기
in Algorithms on BOJ
Graph(DFS)
문제설명
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
접근
입력 값을 통해서는 어떤 노드가 부모 노드이고 자식 노드인지 알 수 없기 때문에 양방향으로 연결여부를 저장해야한다. 모든 입력을 받은 후, 전체 트리의 루트 노드인 1번 노드부터 DFS를 통해 각 노드의 부모를 찾을 수 있다.
코드
#include <iostream>
#include <vector>
#define MAX_NUM 100002
#define ROOT 1
using namespace std;
bool visited[MAX_NUM];
vector<int> tree[MAX_NUM];
int parents[MAX_NUM];
void find_parent(int num){
visited[num] = true;
for(int i=0; i<tree[num].size(); i++){
int nxt = tree[num][i];
if(visited[nxt] == false){
find_parent(nxt);
parents[nxt] = num;
}
}
}
int main(){
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for(int i=0; i<n-1; i++){
int x, y;
cin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}
find_parent(ROOT);
for(int i=2; i<n+1; i++)
cout << parents[i] << '\n';
}
참고
이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)
