Vùng chung nhỏ nhất trong C++

Mô tả bài toán

Cho danh sách các vùng, mỗi danh sách có vùng đầu tiên bao chứa các vùng còn lại. Tìm vùng nhỏ nhất chứa cả hai vùng r1 và r2 cho trước.

Ví dụ: Với cấu trúc:

• Earth → North America, South America
• North America → United States, Canada
• United States → New York, Boston
• Canada → Ontario, Quebec
• South America → Brazil

Giải thuật

1. Xây dựng ánh xạ parent[child] = parent_region từ dữ liệu đầu vào.
2. Tạo tập chain chứa tất cả tổ tiên của r1 (kể cả chính nó).
3. Duyệt lên từ r2 theo cha cho đến khi gặp vùng có trong chain → đó là vùng chung nhỏ nhất (LCA).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& regions, string r1, string r2) {
        unordered_map<string, string> parent;
        for (auto& list : regions) {
            for (int i = 1; i < list.size(); i++) {
                parent[list[i]] = list[0];
            }
        }
        unordered_set<string> chain;
        chain.insert(r1);
        while (parent.count(r1)) {
            r1 = parent[r1];
            chain.insert(r1);
        }
        while (!chain.count(r2)) {
            r2 = parent[r2];
        }
        return r2;
    }
};

int main() {
    vector<vector<string>> v = {
        {"Earth","North America","South America"},
        {"North America","United States","Canada"},
        {"United States","New York","Boston"},
        {"Canada","Ontario","Quebec"},
        {"South America","Brazil"}
    };
    Solution ob;
    cout << ob.findSmallestRegion(v, "Quebec", "New York"); // North America
    return 0;
}

Độ phức tạp

• Thời gian: O(N) (N = tổng số vùng).
• Không gian: O(N) cho map và set.