ภูมิภาคร่วมที่เล็กที่สุดใน C++

ให้รายการภูมิภาคหลายชุด โดยภูมิภาคตัวแรกของแต่ละชุดจะครอบคลุมภูมิภาคอื่นๆ ในชุดนั้น นั่นคือ ถ้า X ครอบคลุม Y แสดงว่า X ใหญ่กว่า Y และทุกภูมิภาคครอบคลุมตัวเองด้วย กำหนดภูมิภาคสองแห่ง r1 และ r2 ต้องการหาภูมิภาคที่เล็กที่สุดที่ครอบคลุมทั้งสองแห่ง

ตัวอย่าง: อินพุต [["Earth","North America","South America"], ["North America","United States","Canada"], ["United States","New York","Boston"], ["Canada","Ontario","Quebec"], ["South America","Brazil"]] และ r1 = "Quebec", r2 = "New York" ผลลัพธ์คือ "North America"

ขั้นตอนการแก้ปัญหา

1. สร้าง map parent เก็บพาเรนต์ของแต่ละภูมิภาค
2. วนลูปทุกชุด: สำหรับ j = 1 ถึงสิ้นสุด ให้ parent[r[i][j]] = r[i][0]
3. สร้างเซต chain ใส่ x (r1) เข้าไป
4. เดินขึ้นตามพาเรนต์ของ x จนหมด ใส่ทุกตัวเข้า chain
5. เดินขึ้นตามพาเรนต์ของ y (r2) จนพบตัวที่อยู่ใน chain
6. คืนค่า y นั้น (คือ LCA / Common Ancestor ที่ลึกที่สุด)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& r, string x, string y) {
        unordered_map<string, string> parent;
        for (auto& vec : r) {
            for (int j = 1; j < vec.size(); j++) {
                parent[vec[j]] = vec[0];
            }
        }
        unordered_set<string> chain;
        chain.insert(x);
        while (parent.count(x)) {
            x = parent[x];
            chain.insert(x);
        }
        while (!chain.count(y)) {
            y = parent[y];
        }
        return y;
    }
};

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");
}

Input

[["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]] "Quebec" "New York"

Output

North America