[ BOJ / C++ ] 11725번 : 트리의 부모 찾기

[ BOJ ] 11725번 : 트리의 부모 찾기

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

---

[  문제  ]

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

[  입력  ]

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

[  출력  ]

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

[  문제 접근 및 풀이  ]

DFS를 통해서 now라는 변수로 현재 노드를 나타냈으며

양방향 간선이기에 현재 노드에서 부모 노드로 갈 수도 있으므로 현재 노드의 부모 노드도

포함시켜 사이클이 도는 것을 방지했다.

이후 현재 노드의 자식 노드를 돌면서

자식 노드의 부모를 현재 노드로 지정 후 DFS를 돌렸다.

 

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> V[100001];
int P[100001];
void Q_11725();
void dfs(int now,int pe);
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_11725();
}
void Q_11725(){
    cin >> N;
    for(int i=1;i<N;i++){
        int a,b;
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    dfs(1,0);
    for(int i=2;i<=N;i++) cout << P[i] <<"\n";
}
void dfs(int now,int pe){
    for(auto x:V[now]){
        if(x==pe) continue;
        P[x]=now;
        dfs(x,now);
    }
}

---