백준 11725 트리의 부모찾기-C++

모든 트리문제를 트리구조로 만들어서 풀 필요는 없다.

코드의 2~4줄의 주석처럼 코딩을 했더라면 아마 100줄이상은 분량이 나왔을거다.

 

문제의 핵심은 각 연결된 두 정점이 있을 때, 둘 중 무엇이 start node고 무엇이 end node인지 모른다는 것이다.

모를 때는 pair로 접근하는 것은 어려운것 같고,

양방향으로 탐색을 해야하기 때문에 벡터에다가 node1 - node2 , node2 - node1 두 가지 모두를 집어넣으면 된다는 점이다.

이렇게 벡터로 트리를 구현한 다음, dfs로 방문 여부를 판단하면서 부모 노드를 기록하면서 진행하면 된다.

////11725번문제
//1. 페어를 각각 만든다
//2. 그걸 벡터에 일단 다 저장해
//3. 트리구조로 만든다음에, 탐색하며 부모찾기? --> 너무복잡. 이렇게 안해도 됨.
 
#include <iostream>
#include <vector>
using namespace std;
int N;
const int MAX=100001;
 
bool visited[MAX];
int parent[MAX];
vector<int> v[MAX];
 
void dfs(int idx){
    visited[idx] = true;
    for(int i=0; i<v[idx].size(); i++){
        int next_idx = v[idx][i];
        if(!visited[next_idx]){
            parent[next_idx]=idx;
            dfs(next_idx);
        }
    }
}
 
int main(void){
    cin>>N;
    for(int i=0; i<N-1; i++){
        int n1,n2;
        cin>>n1>>n2;
        v[n1].push_back(n2);
        v[n2].push_back(n1);
    }
    dfs(1);
    for(int i=2;i<=N; i++)
        cout<<parent[i]<<'\n';
}