[DFS] BOJ 11725 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

문제 해결 알고리즘

 

DFS로 푸는데 각 마디별로 부모를 저장해주고 메모리 초과가 나지 않게 인접행렬보다는 인접리스트를 사용해주었다. 

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int parent[100002];
vector<int> graph[100002];

void find_parent(int x){
  
  for(int i=0;i<graph[x].size();i++){
    if(parent[graph[x][i]] == 0){
      parent[graph[x][i]] = x;
      find_parent(graph[x][i]);
    }
  }

}

int main(){
  int N; cin >> N;

  int A, B;
  for(int i=1;i<N;i++){
    cin >> A >> B;
    graph[A].push_back(B);
    graph[B].push_back(A);
  }

  parent[1] = 1;
  find_parent(1);

  for(int i=2;i<=N;i++){
    cout << parent[i] << '\n';
  }

}