(C++) 백준 3584 가장 가까운 공통 조상

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

평이한 트리문제...

먼저 노드 x의 부모노드를 return해주는 함수 findParent(int x)를 정의하고 다음과 같이 작성했다.

1. 배열에 부모노드를 저장
2. 마지막에 주어진 두 노드의 부모노드를 findParent로 찾아가며 각각 vector에 저장
3. 두 vector를 비교하여 같은 값 찾기

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;


int T,N;
int node[10005]; // memorize parent node
int x,y,A,B;
int ans;
int root;

int findParent(int x){
    return node[x];
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>T;
    while(T--){
        cin>>N;

        memset(node, 0, sizeof(node));
        for(int i=0; i<N-1; i++) {
            cin>>x>>y;
            node[y]=x;
        }

        for(int i=1; i<=N; i++){
            if(node[i]==0){
                root=i;
                break;
            }
        }

        cin>>A>>B;

        vector<int> nodeA;
        vector<int> nodeB;

        while(A!=0 || B!=0) {

            if(A!=0){
                nodeA.push_back(A);
                A = findParent(A);
            }
            if(B!=0){
                nodeB.push_back(B);
                B = findParent(B); 
            }
        }


        bool flag=false;
        for(int i=0; i<nodeA.size(); i++){
            for(int j=0; j<nodeB.size(); j++){
                if(nodeA[i]==nodeB[j]) {
                    ans=nodeA[i];
                    flag=true;
                }
            }
            if(flag) break;
        }

        if(ans==0) ans=root;
        cout<<ans<<'\n';
    }

}