백준 - 3584 가장 가까운 공통 조상

문제 링크입니다 : https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

 

 

시간 복잡도가 O(N)인 방법이다. RMQ로 구현하면 O(logN)으로 구현할 수 있다. 다음 문제들에서는 RMQ로 풀어봐야겠다.

 

 

 

#include <iostream>
#include <vector>

using namespace std;
int T, N;

vector<vector<int>> adj;
vector<int> parent;
vector<int> depth;

void dfs(int here, int d) {
    depth[here] = d;

    for(int i = 0; i < adj[here].size(); i++) {
        int next = adj[here][i];
        dfs(next, d + 1);
    }
}


int main() {
    cin >> T;
    while(T--) {
        cin >> N;
        adj.assign(N + 1, vector<int>());
        parent.assign(N + 1, 0);
        depth.assign(N + 1, 0);

        int u, v;
        for(int i = 0; i < N - 1; i++) {
            cin >> u >> v;
            adj[u].push_back(v);
            parent[v] = u;
        }

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

        dfs(root, 0);


        int a, b;
        cin >> a >> b;

        while(depth[a] != depth[b]) {
            if(depth[a] < depth[b]) {
                b = parent[b];
            } else {
                a = parent[a];
            }
        }
        while(a != b) {
            a = parent[a];
            b = parent[b];
        }
        cout << a << '\n';


    }


    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~