190. LCA 2
54868 ワード
白駿
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));
}
}
Reference
この問題について(190. LCA 2), 我々は、より多くの情報をここで見つけました https://velog.io/@corone_hi/190.-LCA-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol