C ++中最小的公共区域
假设我们有一些区域列表，其中每个列表的第一个区域包括该列表中的所有其他区域。基本上，如果区域X包含另一个区域Y，则X大于Y。同样，根据定义，区域X包含自身。因此，如果我们有两个区域r1和r2，则必须找到包含两个区域的最小区域。因此，如果我们拥有r1，r2和r3使得r1包括r3，则可以保证没有r2使得r2包括r3。因此，如果输入类似于[[“Earth”，“NorthAmerica”，“SouthAmerica”]，[“NorthAmerica”，“UnitedStates”，“Canada”]，[“UnitedStates”，“NewYork”，“波士顿”]，[“加拿大”，“安大略省”，“魁北克”]，[“南美”，“巴西”]]，并且r1='Quebec'和r2='NewYork'，
为了解决这个问题，我们将遵循以下步骤-
创建一个称为父级的映射
当我在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