190. LCA 2

백준

1. Python

DFS, DP

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e5))
LOG = 21 #2^20 = 1,000,000 최대 백만개의 데이터 처리 가능 (비트 수)

n = int(input())
parent = [[0] * LOG for _ in range(n + 1)]
d = [0] * (n + 1) #각 노드까지의 깊이
c = [0] * (n + 1) #각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)]

for _ in range(n - 1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

#루트 노드부터 깊이 탐색
def dfs(x, depth):
  c[x] = True
  d[x] = depth
  for y in graph[x]:
    if c[y]:
      continue
    parent[y][0] = x # 2^0d으로 일단 한칸 앞에 있는 부모부터 구한다.
    dfs(y, depth + 1)

#전체 부모 관계 설정
def set_parent():
  dfs(1, 0)
  for i in range(1, LOG):
    for j in range(1, n + 1): 
      #2의 제곱 꼴로 뛰었을 때의 부모 기록 (2, 4, 8, 16 ...) 앞에 있는 부모
      parent[j][i] = parent[parent[j][i - 1]][i - 1]

#A와 B의 최소 공통 조상 찾기
def lca(a, b):
  #b가 더 깊도록 설정
  if d[a] > d[b]:
    a, b = b, a
  #먼저 깊이가 동일하도록
  #큰 크기부터 작은 크기 방향으로 이동 (15만큼 깊이 차이가 난다면 8, 4, 2, 1 로 15만큼 줄일 수 있게 한다.)
  for i in range(LOG - 1, -1, -1): 
  	#깊이 차이가 크다면 2의 제곱 꼴로 뛸 수 있도록 한다.
    if d[b] - d[a] >= (1 << i):
      b = parent[b][i]
  #부모가 같아지도록
  if a == b:
    return a
  for i in range(LOG - 1, -1, -1):
    if parent[a][i] != parent[b][i]:
      a = parent[a][i]
      b = parent[b][i]
  #이후에 부모가 찾고자 하는 조상
  return parent[a][0]

set_parent()
m = int(input())

for i in range(m):
  a, b = map(int, input().split())
  print(lca(a, b))

2. C++

// 최저공통조상.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 100005
#define PIV 17
using namespace std;
vector<int> con[MAX];
int dep[MAX];
int par[PIV][MAX];
int lca(int a, int b)
{
    int tmp;
    if (dep[b] < dep[a]) tmp = a, a = b, b = tmp; // b의 depth 가 더 깊게
    tmp = dep[b] - dep[a];
    for (int i = 0; i < PIV; i++)
    {
        int bit = (1 << i);
        if ((tmp & bit) == bit)
            b = par[i][b];
    }
    if (b == a) return a; // a 가 바로 lca 이므로 리턴

    for (int i = PIV - 1; i >= 0; i--)
    {
        if (par[i][a] != par[i][b])
            a = par[i][a], b = par[i][b];
    }
    return par[0][a];
}
int main()
{
    /*
    int n = 21;
    int k = 7;
    int mod = 11;
    // k를 n번 곱한 수의 mod 로 나눈 나머지
    // 21 = 10101(2)
    int ret = 1;
    int seven[100];
    seven[0] = 7;
    for (int i = 1; i < 10; i++)
        seven[i] = (seven[i - 1] * seven[i - 1]) % mod;
    // seven[i] : 7을 2의i제곱한 값 (의 mod나머지)
    int val = 1;
    for (int bit = 0; bit <= 10; bit++)
    {
        //int val = (1 << bit);
        if ((n & val) == val)
            ret = (ret * seven[bit]) % mod;
        val *= 2;
    }
    printf("%d\n", ret);
    return 0;
    */

    int M, N, a, b;
    scanf("%d", &N);
    for (int i = 1; i <= N - 1; i++)
    {
        scanf("%d %d", &a, &b);
        con[a].push_back(b);
        con[b].push_back(a);
        dep[i] = 0;
    }
    queue<int> que;
    que.push(1); // value
    que.push(1); // depth
    int depth = 0;
    while (que.empty() == false)
    {
        int val = que.front(); que.pop();
        depth = que.front(); que.pop();
        dep[val] = depth;
        for (int next : con[val])
        {
            if (dep[next] == 0)
            {
                par[0][next] = val; // 부모를 저장
                que.push(next);
                que.push(depth + 1);
            }
        }
    }
    //par[0][j] : 1조상, par[1][j] : 2조상, par[2][j] : 4조상... 
    for (int i = 1; i < PIV; i++)
        for (int j = 1; j <= N; j++)
            par[i][j] = par[i - 1][par[i - 1][j]];

    scanf("%d", &M);
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

DP, BFS

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;

void BFS(vector<int> *node, int *parent, int *depth, int V, int start)
{
    queue<int> q;
    bool check[V + 1] = {false};

    check[start] = true;
    parent[start] = 0;
    depth[start] = 0;
    q.push(start);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int i = 0; i < node[now].size(); i++)
        {
            int next = node[now][i];
            if (!check[next])
            {
                parent[next] = now;
                depth[next] = depth[now] + 1;
                check[next] = true;
                q.push(next);
            }
        }
    }
}

void makeGraph(vector<int> *node, int *parent, int *depth, int V)
{
    int E = V - 1;
    while (E--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        node[u].push_back(v);
        node[v].push_back(u);
    }
    BFS(node, parent, depth, V, 1);
}

void makeLCA(int *parent, int *depth, vector<vector<int>> &LCA, int V)
{
    int log;
    for (log = 1; (1 << log) <= V; log++)
        ;

    for (int i = 0; i <= V; i++)
    {
        vector<int> tmp(log, 0);
        LCA[i] = tmp;
    }

    for (int i = 1; i <= V; i++)
        LCA[i][0] = parent[i];

    for (int j = 1; (1 << j) < V; j++)
        for (int i = 1; i <= V; i++)
            if (LCA[i][j - 1] != 0)
                LCA[i][j] = LCA[LCA[i][j - 1]][j - 1];
}

int findLCA(vector<vector<int>> &LCA, int *depth, int u, int v)
{
    if (depth[u] < depth[v])
        swap(u, v);

    // depth[u] > depth[v]
    int log = 1;
    for (log = 1; (1 << log) <= depth[u]; log++)
    {
    }
    log--;

    for (int i = log; i >= 0; i--)
        if (depth[u] - (1 << i) >= depth[v])
            u = LCA[u][i];

    if (u == v)
        return u;
    else
    {
        for (int i = log; i >= 0; i--)
            if (LCA[u][i] != 0 && LCA[u][i] != LCA[v][i])
            {
                u = LCA[u][i];
                v = LCA[v][i];
            }
        return LCA[u][0];
    }
}

int main()
{
    int N;
    scanf("%d", &N);

    vector<int> node[N + 1];
    int parent[N + 1];
    int depth[N + 1];
    makeGraph(node, parent, depth, N);

    vector<vector<int>> LCA(N + 1);
    makeLCA(parent, depth, LCA, N);

    int M;
    scanf("%d", &M);
    while (M--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d\n", findLCA(LCA, depth, u, v));
    }
}