트리의 부모 찾기 백준 - 11725번

DFS문제 입니다. 

처음에는 순서대로 입력받는 줄 알고, 풀었다가 틀린뒤, DFS()을 이용하여 풀었습니다. 

입력을 받을 때, 뭐가 부모이고, 자식노드 인지 정해주지 않기 때문에, 입력을 모두 받은 다음에, 1(root node)부터 자식노드 순으로 내려오면서, 부모-자식관계를 연결하고자 했습니다.

 

#import<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(int i=0;i<j;i++)
#define mrep(i,j,k) for(int i = j; i<=k;i++)
#define pb push_back

vector<int> arr[100001];
bool visited[100001];
int parent[100001];

void Parent(int i){//dfs
    visited[i] = true;
    int size = arr[i].size();
    rep(j,size){
        if(!visited[arr[i][j]]){
            parent[arr[i][j]] = i;
            Parent(arr[i][j]);
        }
    }
}
int main(){
	fast_io;
    int n;
    cin>>n;
    int x,y;
    rep(i,n-1){
        cin>>x>>y;
        arr[x].pb(y);
        arr[y].pb(x);
    }//양방향으로 연결.
    Parent(1);
    mrep(i,2,n){
        cout<<parent[i]<<endl;
    }
}

www.acmicpc.net/problem/11725