[백준] 3584번 가장 가까운 공통 조상

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

문제의 설명은 다음과 같습니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.
  
• 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

이 문제는 아래와 같이 풀수 있습니다.

• 주어진 두 노드를 각각 a,b라고 하자
• 1. a의 부모들을 저장하는 set_a,b의 부모들을 저장하는 set_b 을 만든다.
• 2. a의 부모로 이동하고 그 부모를 parent_a라고 하자
     b의 부모로 이동하고 그 부모를 parent_b라고 하자
     parent_a를 set_a,parent_b를 set_b에 넣는다.
     • 2-1 아래를 검사한다.
       • parent_a가 set_b의 원소이면 정답은 parent_a
         parent_b가 set_a의 원소이면 정답은 parent_b 이다.
     • 2-1이 false일 경우 a=parent_a,b=parent_b로 갱신하고 다시 2를 한다.

코드

#include <bits/stdc++.h>
using namespace std;
int parentReturn(vector<pair<int,vector<int> > > &v,int child){
  return v[child].first;
}
int BFS_search(vector<pair<int,vector<int> > > &v,int child1,int child2){
  set<int> parent1;
  set<int> parent2;
  parent1.insert(child1);
  parent2.insert(child2);
    while(true){
      if(parent2.find(child1)!=parent2.end()) return child1;
      else if(parent1.find(child2)!=parent1.end()) return child2;
      if(child1!=-1){
        child1=parentReturn(v,child1);
        parent1.insert(child1);
      }
      if(child2!=-1){
      child2=parentReturn(v,child2);
      parent2.insert(child2);
      }
    }
}
int main(void){
  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int testcase,n,parent,child;
  cin>>testcase;
  for(int j=0;j<testcase;j++){
    cin>>n;
    vector<pair<int,vector<int> > > v(n+1,{-1,vector<int>(0)});
    for(int i=0;i<n-1;i++){
      cin>>parent>>child;
      v[parent].second.push_back(child);
      v[child].first=parent;
    }
    cin>>parent>>child;
    cout<<BFS_search(v,parent,child)<<"\n";
  }

  return 0;
}