Khóa học CTDL và GT

Bài 24.5. Bài tập cơ bản về LCA

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một khái niệm cực kỳ quan trọng khi làm việc với cấu trúc cây: Cây Tổ Tiên Chung Nhất, hay viết tắt là LCA (Lowest Common Ancestor). Nghe tên có vẻ hơi "huyền bí", nhưng thực ra nó mô tả một mối quan hệ rất tự nhiên trong cây. Hãy cùng tìm hiểu xem LCA là gì, tại sao nó lại hữu ích và làm thế nào để tìm được nó một cách hiệu quả nhé!

LCA là gì? Bài toán LCA

Hãy tưởng tượng một cây gia phả. Tổ tiên chung của hai người là bất kỳ ai mà cả hai đều là hậu duệ. Tổ tiên chung nhất (LCA) của hai người đó chính là người tổ tiên chung ở tầng thấp nhất (gần hai người đó nhất).

Trong thuật ngữ của tin học, với một cây có gốc (rooted tree) và hai nút bất kỳ u và v:

• Một nút w là tổ tiên của u nếu w nằm trên đường đi từ gốc đến u (bao gồm cả u).
• w là tổ tiên chung của u và v nếu w vừa là tổ tiên của u vừa là tổ tiên của v.
• w là tổ tiên chung nhất (LCA) của u và v nếu w là tổ tiên chung của u và v và nó có độ sâu lớn nhất (tức là xa gốc nhất) trong tất cả các tổ tiên chung.

Bài toán LCA đơn giản là: Cho một cây có gốc và hai nút u, v, tìm LCA của u và v.

Tại sao LCA lại quan trọng?

LCA không chỉ là một khái niệm lý thuyết. Nó có rất nhiều ứng dụng thực tế trong tin học:

• Hệ thống tập tin: Tìm thư mục chung gần nhất chứa hai tệp.
• Sinh học: Phân tích cây phát sinh loài (phylogenetic trees) để tìm tổ tiên chung gần nhất của hai loài.
• Mạng máy tính: Định tuyến trong các mạng cây.
• Lập trình thi đấu: LCA là nền tảng cho nhiều bài toán phức tạp hơn trên cây, ví dụ như tính khoảng cách giữa hai nút, hay các bài toán liên quan đến đường đi.

Các phương pháp cơ bản tìm LCA

Có nhiều cách để tìm LCA, từ đơn giản đến phức tạp, với hiệu suất khác nhau. Hôm nay, chúng ta sẽ tập trung vào một phương pháp cơ bản nhưng rất trực quan, dựa trên việc điều chỉnh độ sâu và duyệt đồng thời lên phía gốc.

Phương pháp: Điều chỉnh độ sâu và Duyệt đồng thời

Ý tưởng chính của phương pháp này là đưa hai nút u và v về cùng một độ sâu, sau đó cùng lúc di chuyển cả hai lên phía gốc cho đến khi chúng gặp nhau. Nút gặp nhau chính là LCA.

Để làm được điều này, chúng ta cần thông tin về cây:

1. Độ sâu (depth) của mỗi nút: Khoảng cách từ gốc đến nút đó (gốc có độ sâu 0 hoặc 1 tùy quy ước).
2. Nút cha (parent) trực tiếp của mỗi nút: Ngoại trừ gốc.

Chúng ta có thể tính toán hai thông tin này bằng cách thực hiện một lần duyệt cây, ví dụ như Duyệt theo chiều sâu (DFS), bắt đầu từ gốc.

Các bước thực hiện:

1. Tiền xử lý (DFS): Duyệt cây từ gốc để tính toán depth[i] và parent[i] cho mọi nút i. parent[root] có thể đặt là null hoặc chính nó.
2. Xử lý truy vấn (tìm LCA của u và v):
   • Bước 2a: Điều chỉnh độ sâu. Nếu depth[u] khác depth[v], di chuyển nút ở độ sâu lớn hơn lên phía gốc cho đến khi độ sâu của nó bằng với nút kia. Ví dụ, nếu depth[u] > depth[v], gán u = parent[u] cho đến khi depth[u] == depth[v].
   • Bước 2b: Kiểm tra trường hợp đặc biệt. Sau khi điều chỉnh độ sâu, nếu u == v, điều đó có nghĩa là một nút ban đầu là tổ tiên của nút kia. Nút này (hiện tại là u hoặc v) chính là LCA.
   • Bước 2c: Duyệt đồng thời. Nếu u != v, di chuyển cả hai nút u và v lên phía gốc đồng thời từng bước một (u = parent[u], v = parent[v]) cho đến khi u == v. Nút mà chúng gặp nhau chính là LCA.

Ví dụ Minh họa

Xét cây có gốc là nút 1 sau:

       1 (depth 0)
      / \
     2   3 (depth 1)
    / \   \
   4   5   6 (depth 2)
      /   / \
     7   8   9 (depth 3)

Thông tin parent và depth sau khi DFS từ gốc 1:

Truy vấn 1: Tìm LCA(7, 9)

• u = 7, v = 9.
• depth[7] = 3, depth[9] = 3. Độ sâu bằng nhau, không cần điều chỉnh.
• u != v. Duyệt đồng thời:
  • u = parent[7] = 5, v = parent[9] = 6. (u != v)
  • u = parent[5] = 2, v = parent[6] = 3. (u != v)
  • u = parent[2] = 1, v = parent[3] = 1. (u == v! Chúng gặp nhau tại nút 1).
• LCA(7, 9) là 1.

Truy vấn 2: Tìm LCA(8, 6)

• u = 8, v = 6.
• depth[8] = 3, depth[6] = 2. depth[8] > depth[6].
• Điều chỉnh độ sâu: u = parent[8] = 6. Bây giờ u = 6, v = 6.
• u == v. Chúng gặp nhau ngay sau khi điều chỉnh.
• LCA(8, 6) là 6. (Điều này đúng vì 6 là tổ tiên của 8).

Truy vấn 3: Tìm LCA(4, 5)

• u = 4, v = 5.
• depth[4] = 2, depth[5] = 2. Độ sâu bằng nhau.
• u != v. Duyệt đồng thời:
  • u = parent[4] = 2, v = parent[5] = 2. (u == v! Chúng gặp nhau tại nút 2).
• LCA(4, 5) là 2.

Phương pháp này khá đơn giản và dễ hiểu phải không?

C++ Code Minh họa

Bây giờ, chúng ta sẽ hiện thực hóa phương pháp này bằng C++. Chúng ta cần một hàm DFS để tiền xử lý và một hàm findLCA để xử lý các truy vấn.

#include <iostream>
#include <vector>
#include <algorithm> // for swap

using namespace std;

const int MAXN = 1005; // Kích thước tối đa của cây
vector<int> adj[MAXN]; // Danh sách kề biểu diễn cây
int parent[MAXN];      // Mảng lưu nút cha
int depth[MAXN];       // Mảng lưu độ sâu
int n;                 // Số lượng nút trong cây

// Hàm DFS để tính toán parent và depth
// u: nút hiện tại, p: nút cha của u, d: độ sâu của u
void dfs(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    for (int v : adj[u]) {
        if (v != p) { // Đảm bảo không đi ngược lại về nút cha
            dfs(v, u, d + 1);
        }
    }
}

// Hàm tìm LCA của hai nút u và v
int findLCA(int u, int v) {
    // Bước 2a: Điều chỉnh độ sâu
    // Đưa nút có độ sâu lớn hơn lên bằng với nút kia
    while (depth[u] > depth[v]) {
        u = parent[u];
    }
    while (depth[v] > depth[u]) {
        v = parent[v];
    }

    // Bước 2b & 2c: Kiểm tra và duyệt đồng thời
    // Nếu đã cùng nút, đó là LCA
    if (u == v) {
        return u;
    }

    // Di chuyển đồng thời lên phía gốc cho đến khi gặp nhau
    while (parent[u] != parent[v]) {
        u = parent[u];
        v = parent[v];
    }

    // Khi parent[u] == parent[v], nút cha chung đó chính là LCA
    // (trừ trường hợp u và v là con trực tiếp của LCA)
    // Nút cha đó là LCA
    return parent[u];
}

int main() {
    // Xây dựng cây ví dụ
    // Nút 1 là gốc
    n = 9;
    adj[1].push_back(2); adj[1].push_back(3);
    adj[2].push_back(1); adj[2].push_back(4); adj[2].push_back(5);
    adj[3].push_back(1); adj[3].push_back(6);
    adj[4].push_back(2);
    adj[5].push_back(2); adj[5].push_back(7);
    adj[6].push_back(3); adj[6].push_back(8); adj[6].push_back(9);
    adj[7].push_back(5);
    adj[8].push_back(6);
    adj[9].push_back(6);

    // Bước 1: Tiền xử lý - Chạy DFS từ gốc (nút 1)
    // Nút cha của gốc (1) có thể để là 0 hoặc 1 tùy quy ước, ở đây để là 0 tạm
    dfs(1, 0, 0); // Bắt đầu từ gốc 1, cha là 0, độ sâu 0

    // Kiểm tra kết quả DFS (ví dụ)
    // for(int i = 1; i <= n; ++i) {
    //     cout << "Node " << i << ": parent = " << parent[i] << ", depth = " << depth[i] << endl;
    // }

    // Thử nghiệm với các truy vấn LCA
    cout << "LCA(7, 9) is: " << findLCA(7, 9) << endl; // Expected: 1
    cout << "LCA(8, 6) is: " << findLCA(8, 6) << endl; // Expected: 6
    cout << "LCA(4, 5) is: " << findLCA(4, 5) << endl; // Expected: 2
    cout << "LCA(7, 5) is: " << findLCA(7, 5) << endl; // Expected: 5 (7 là con của 5)
    cout << "LCA(4, 6) is: " << findLCA(4, 6) << endl; // Expected: 1
    cout << "LCA(1, 9) is: " << findLCA(1, 9) << endl; // Expected: 1 (1 là gốc)

    return 0;
}

Giải thích Code C++

1. Includes và Khai báo:

   • iostream, vector, algorithm: Các thư viện cần thiết cho nhập xuất, sử dụng vector (danh sách kề) và hàm swap (mặc dù tôi đã thay đổi logic để không cần swap trực tiếp u, v mà chỉ điều chỉnh nút sâu hơn).
   • MAXN: Hằng số định nghĩa kích thước tối đa của cây, giúp khai báo mảng tĩnh.
   • adj[MAXN]: Mảng các vector để biểu diễn cây dưới dạng danh sách kề. adj[i] chứa các nút kề với nút i. Vì đây là cây vô hướng khi đọc input, chúng ta thêm cạnh ở cả hai chiều. Tuy nhiên, khi duyệt DFS, chúng ta sẽ coi nó như cây có gốc.
   • parent[MAXN]: Mảng lưu trữ nút cha trực tiếp của mỗi nút. parent[i] là cha của nút i.
   • depth[MAXN]: Mảng lưu trữ độ sâu của mỗi nút. depth[i] là khoảng cách từ gốc đến nút i.
   • n: Biến lưu số lượng nút.

2. Hàm dfs(int u, int p, int d):

   • Đây là hàm đệ quy để duyệt cây theo chiều sâu, bắt đầu từ u.
   • p là nút cha của u trong quá trình duyệt hiện tại.
   • d là độ sâu của u.
   • parent[u] = p;: Gán cha của nút u là p.
   • depth[u] = d;: Gán độ sâu của nút u là d.
   • Vòng lặp for (int v : adj[u]): Duyệt qua tất cả các nút kề v với u.
   • if (v != p): Kiểm tra để đảm bảo v không phải là nút cha mà từ đó chúng ta vừa đi xuống u. Điều này quan trọng để tránh đi ngược lên trong quá trình DFS trên biểu diễn đồ thị vô hướng.
   • dfs(v, u, d + 1);: Gọi đệ quy cho nút con v, với u là cha của v và độ sâu tăng lên 1.

3. Hàm findLCA(int u, int v):

   • Hàm này nhận hai nút u và v và trả về LCA của chúng.
   • Điều chỉnh độ sâu: Hai vòng while đầu tiên thực hiện Bước 2a. Nếu u sâu hơn v, di chuyển u lên bằng cách gán u = parent[u]. Lặp lại cho đến khi depth[u] không còn lớn hơn depth[v]. Sau đó, làm tương tự với v nếu v sâu hơn u. Khi kết thúc hai vòng lặp này, u và v sẽ có cùng độ sâu.
   • Kiểm tra gặp nhau sớm: if (u == v): Nếu sau khi điều chỉnh độ sâu mà u và v đã là cùng một nút, điều này chỉ xảy ra khi một nút ban đầu là tổ tiên của nút kia. Nút đó chính là LCA, nên ta trả về u (hoặc v).
   • Duyệt đồng thời: Vòng while (parent[u] != parent[v]) thực hiện Bước 2c. Chừng nào cha của u và cha của v còn khác nhau, ta di chuyển cả u lẫn v lên một bước bằng cách gán u = parent[u] và v = parent[v].
   • Tìm thấy LCA: Khi vòng lặp kết thúc, điều kiện parent[u] != parent[v] không còn đúng, tức là parent[u] == parent[v]. Nút cha chung này chính là LCA của u và v. Lưu ý rằng u và v lúc này đang đứng ở hai nút con của LCA, và chúng có chung một cha. Nút cha đó là LCA. Ta trả về parent[u] (hoặc parent[v]).

4. Hàm main():

   • Xây dựng cấu trúc cây bằng cách thêm các cạnh vào danh sách kề adj. Lưu ý: vì DFS được gọi từ gốc 1, cây sẽ được coi là có hướng từ 1 đi xuống, mặc dù danh sách kề được thêm hai chiều.
   • Gọi dfs(1, 0, 0) để tiền xử lý. Gốc là 1, cha của gốc quy ước là 0 (một giá trị không tồn tại trong tập nút {1..n}), độ sâu của gốc là 0.
   • Thực hiện các truy vấn findLCA với các cặp nút khác nhau và in kết quả.

Độ phức tạp

• Tiền xử lý (DFS): Duyệt qua mỗi cạnh và mỗi nút một lần. Độ phức tạp thời gian là O(N + M), trong đó N là số nút và M là số cạnh. Trong cây, M = N-1, nên là O(N). Độ phức tạp không gian là O(N) để lưu trữ danh sách kề, mảng parent và depth.
• Truy vấn (findLCA): Trong trường hợp xấu nhất (cây suy biến thành danh sách liên kết), để điều chỉnh độ sâu hoặc di chuyển đồng thời, chúng ta có thể phải đi lên tới H bước, trong đó H là chiều cao của cây. Độ phức tạp thời gian cho mỗi truy vấn là O(H). Trong trường hợp xấu nhất, H = N.