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/