lca.cpp (3)
Bài toán
Tìm LCA (tổ tiên chung gần nhất) giữa hai nút x và y trên cây có gốc.
Độ phức tạp
khởi tạo: O(n logn)
truy vấn: O(logn)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define long long long
#define N 100005
int n, m, t, T, Root;
int Parent[21][N], Level[N]; //
int level(int u) { // recursion because n<=1000
if (u == Root) return 1;
if (Level[u]) return Level[u];
return Level[u] = level(Parent[0][u]) + 1;
}
void enter() {
for (int i = 1; i <= n; ++i) {
int x, y;
scanf("%d", &y);
while (y--) {
scanf("%d", &x);
Parent[0][x] = i;
}
}
for (int i = 1; i <= n; ++i) if (Parent[0][i] == 0) Root = i;
}
int lca(int x, int y) {
#define k(x) Parent[k][x]
for (int k = 20; k >= 0; k--)
if (level(k(x)) >= level(y)) x = k(x);
for (int k = 20; k >= 0; k--)
if (level(k(y)) >= level(x)) y = k(y);
for (int k = 20; k >= 0; k--)
if (k(x) != k(y)) x = k(x), y = k(y);
while (x != y) {
x = Parent[0][x], y = Parent[0][y];
}
#undef k
return x;
}
int main() {
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) Parent[0][i] = Level[i] = 0; // init
enter();
Parent[0][Root] = Root;
for (int k = 1; k <= 20; k++)
for (int i = 1; i <= n; i++)
Parent[k][i] = Parent[k - 1][Parent[k - 1][i]];
printf("Case %d:\n", t);
scanf("%d", &m);
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
}
}
Mô tả
int Parent[k][x]
tổ tiên thứ 2^k của x, Parent[0][x] là cha trực tiếp của x.
int level(x)
độ sâu của nút x, level(Root)=1 (thực ra level(Root) bằng 0 hay 1 cũng được).
Nhận xét
Code này đã được dùng để nộp cho một bài trên SPOJ.
Tham khảo
http://www.spoj.com/problems/LCA/