Lowest common ancestor(LCA)
LCA
트리에서 서로 다른 두 노드에 대해 루트노드에서 가장 멀리 있는 공통 조상을 LCA라고 합니다.
위의 그림에서 검은색 노드의 LCA는 빨간색 입니다.
LCA를 찾는 방법은
1. 두 노드의 dept를 맞춘다.
2. 두 노드가 같아질때까지 계속 위로 올라간다.
2단계롤 나눌수 있습니다.
가장 쉽게 구현할수 있는 방법은 하나씩 올라가는 것입니다. 이 경우엔 최악의 경우 O(n)의 시간 복잡도를 가지게 됩니다.
더 빠르게 구현하기 위해서 '희소테이블' 이라는 테크닉을 이용할 수 있습니다.
즉 하나씩 올라가는 것이 아니라 가능한 최대한 멀리 올라가는 것이지요.
예를들어 두 노드 A, B의 LCA인 C노드의 깊이가 3이고
A의 깊이는 100, B의 깊이는 200 이라고 하면, 하나씩 올라가는것은 너무 정직하게 올라가는 것이죠.
한칸이 아닌 여러칸씩 올라가게 되면 훨씬더 빠르게 LCA를 찾을 수 있습니다.
희소테이블에
parent[i][j] : i노드의 2^j위에 있는 노드
의 규칙으로 저장하고 올라가게 된다면 A, B노드의 깊이를 같게 만드는데 100번의 연산이 아닌 3번의 연산으로 해결할 수 있습니다.(low하게 올라가면 하나씩 올라가 100번의 시도를 해야 하지만 희소테이블을 사용하면 100의 이진수 표현 1100100 에서 유효한 1이 3개라 3번이면 올라갈 수 있습니다.) 즉 최악의 경우에도 O(lgn)이면 LCA를 찾을 수 있습니다.
구현은 밑의 문제로 대신하겠습니다.
https://www.acmicpc.net/problem/11438
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
//11438 - LCA 2
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> adj;
vector<bool> visit;
int parent[100001][18];
int dept[100001];
void dfs(int here)
{
for(int i = 0; i<adj[here].size(); ++i)
{
int there = adj[here][i];
if(!visit[there])
{
visit[there] = true;
dept[there] = dept[here] + 1;
parent[there][0] = here;
dfs(there);
}
}
}
void init()
{
cin >> N;
adj = vector<vector<int>>(N+1);
visit = vector<bool>(N+1, false);
int x, y;
for (int i = 1; i <= N; ++i)
for (int j = 0; j < 18; ++j)
parent[i][j] = -1;
parent[1][0] = 1;
dept[1] = 0;
for (int i = 0; i < N - 1; ++i)
{
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
visit[1] = true;
dfs(1);
for (int j = 1; j < 17; ++j)
for (int i = 1; i <= N; ++i)
parent[i][j] = parent[parent[i][j - 1]][j - 1];
cin >> M;
}
int lastOneBit(int u)
{
int ret = 0;
while (u % 2 == 0)
{
u /= 2;
++ret;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int u, v;
for (int i = 0; i < M; ++i)
{
cin >> u >> v;
if (dept[u] < dept[v])
swap(u, v);
int gap = dept[u] - dept[v];
while (gap)
{
u = parent[u][lastOneBit(gap)];
gap &= (gap - 1);
}
while (u != v)
{
for (int j = 17; j >= 0; --j)
if (parent[u][j] != -1 && parent[u][j] != parent[v][j])
{
u = parent[u][j], v = parent[v][j];
break;
}
u = parent[u][0], v = parent[v][0];
}
cout << u << "\n";
}
}
|
cs |