C++で最小の共通領域

各リストの最初のリージョンにそのリスト内の他のすべてのリージョンが含まれているリージョンのリストがあるとします。基本的に、領域Xに別の領域Yが含まれている場合、XはYよりも大きくなります。また、定義上、領域Xにはそれ自体が含まれます。したがって、2つの領域r1とr2がある場合、両方を含む最小の領域を見つける必要があります。したがって、r1にr3が含まれるようなr1、r2、およびr3がある場合、r2にr3が含まれるような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='NewYork'の場合、出力は次のようになります。 「北米」

これを解決するには、次の手順に従います-

• 親と呼ばれる地図を作成する
• 0からrのサイズまでの範囲のiの場合
  • 範囲1からr[i]のサイズのjの場合
    • 親[r[i、j]]：=r [i、0]
• チェーンと呼ばれる1つのセットを作成し、xをチェーンに挿入します
• xが親にある間、
  • x：=parent [x]
  • xをチェーンに挿入
• yがチェーンに存在する間
  • y：=parent [y]
• yを返す

理解を深めるために、次の実装を見てみましょう-

例

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

入力

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

出力

North America