C ++中最小的公共区域

假设我们有一些区域列表，其中每个列表的第一个区域包括该列表中的所有其他区域。基本上，如果区域X包含另一个区域Y，则X大于Y。同样，根据定义，区域X包含自身。因此，如果我们有两个区域r1和r2，则必须找到包含两个区域的最小区域。因此，如果我们拥有r1，r2和r3使得r1包括r3，则可以保证没有r2使得r2包括r3。因此，如果输入类似于[[“ Earth”，“ North America”，“ South America”]，[“ North America”，“ United States”，“ Canada”]，[“ United States”，“ New York”， “波士顿”]，[“加拿大”，“安大略省”，“魁北克”]，[“南美”，“巴西”]]，并且r1 ='Quebec'和r2 ='New York'，

为了解决这个问题，我们将遵循以下步骤-

• 创建一个称为父级的映射

• 当我在0到r的范围内时

• parent [r [i，j]]：= r [i，0]

• 对于范围1到j [r]的j

• 创建一组称为链的链，然后将x插入链

• 当x在父级中时，

• x：=父母[x]

• 将x插入链中

• 当y存在于链中时

• y：=父母[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