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

문제

www.acmicpc.net/problem/3584

알고리즘

DFS, LCA

 

풀이

그래프가 주어지고 두개의 정점이 주어졌을 때, LCA를 구하는 문제입니다.

 

LCA를 나이브하게 처리하는 방법은 루트 정점을 구한 후 그 정점으로부터 다른정점들의 깊이를 구합니다. 그리고 처리해야할 두 정점 $u$,$v$를 입력받으면 두 정점이 같아질 때까지 깊이를 기준으로 하나씩 정점을 위로 보내면 됩니다.

깊이를 처리해야하는 시간복잡도는 $O(N)$이고 worst case 또한 모든 간선을 다 탐색하는 것이므로 $O(N)$입니다. 이 문제는 Testcase의 수가 적어 $O(T*N)$에 처리됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

const int MAXN = 10000;

int tc,N,u,v;
int p[MAXN],dep[MAXN],check[MAXN];
vector<vector<int>> adj;
void dfs(int here) {
    for (auto there : adj[here]) {
        if (there ^ p[here]) {
            dep[there] = dep[here] + 1;
            dfs(there);
        }
    }
}

int getParent(int u, int v) {
    while (u^v) {
        if (dep[u] < dep[v]) swap(u, v);
        u = p[u];
    }
    return u;
}

int main() {
    FAST;
    cin >> tc;
    while (tc--) {
        cin >> N;
        memset(check, 0, sizeof(check));
        adj.clear();
        adj.resize(N);
        int rt = -1;
        rep(i, N - 1) {
            cin >> u >> v;
            --u, --v;
            if (check[v] == 0) check[v] = 1;
            p[v] = u;
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }
        rep(i, N) {
            if (!check[i]) {
                rt = i;
                break;
            }
        }
        dfs(rt);
        cin >> u >> v;
        --u, --v;
        cout << getParent(u, v) + 1 << '\n';
    }
    return 0;
}

++

코드에 등장하는 XOR 연산은 != 와 동일합니다. 같은 수를 XOR하면 0이 되기 때문입니다.