Khu vực chung nhỏ nhất trong C ++

Giả sử chúng ta có một số danh sách các vùng mà vùng đầu tiên của mỗi danh sách bao gồm tất cả các vùng khác trong danh sách đó. về cơ bản, nếu một vùng X chứa một vùng Y khác thì X lớn hơn Y. Cũng theo định nghĩa, một vùng X chứa chính nó. Vì vậy, nếu chúng ta có hai vùng r1 và r2, chúng ta phải tìm vùng nhỏ nhất chứa cả hai vùng đó. Vì vậy, nếu chúng ta có r1, r2 và r3 sao cho r1 bao gồm r3, nó được đảm bảo không có r2 mà r2 bao gồm r3. Vì vậy, nếu đầu vào là [["Earth", "Bắc Mỹ", "Nam Mỹ"], ["Bắc Mỹ", "Hoa Kỳ", "Canada"], ["Hoa Kỳ", "New York", "Boston"], ["Canada", "Ontario", "Quebec"], ["Nam Mỹ", "Brazil"]] và r1 ='Quebec' và r2 ='New York', thì đầu ra sẽ là 'Bắc Mỹ'

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một bản đồ có tên gốc
• cho tôi trong phạm vi từ 0 đến kích thước của r
  • cho j trong phạm vi 1 đến kích thước của r [i]
    • parent [r [i, j]]:=r [i, 0]
• tạo một tập hợp được gọi là chuỗi và chèn x vào chuỗi
• trong khi x ở trong cha mẹ,
  • x:=cha [x]
  • chèn x vào chuỗi
• trong khi y hiện diện trong chuỗi
  • y:=parent [y]
• trả lại y

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string findSmallestRegion(vector<vector<string>>& r, string x, string y) {
      map < string, string> parent;
      for(int i = 0; i < r.size(); i++){
         for(int j = 1; j < r[i].size(); j++){
            parent[r[i][j]] = r[i][0];
         }
      }
      set <string> chain;
      chain.insert(x);
      while(parent.find(x)!=parent.end()){
         x = parent[x];
         chain.insert(x);
      }
      while(chain.find(y)==chain.end()){
         y = parent[y];
      }
      return y;
   }
};
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"));
}

Đầu vào

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

Đầu ra

North America