C++에서 가장 작은 공통 영역

각 목록의 첫 번째 지역이 해당 목록의 다른 모든 지역을 포함하는 지역 목록이 있다고 가정합니다. 기본적으로 영역 X가 다른 영역 Y를 포함하는 경우 X는 Y보다 큽니다. 또한 정의에 따라 영역 X는 자체를 포함합니다. 따라서 두 개의 영역 r1과 r2가 있는 경우 두 영역을 모두 포함하는 가장 작은 영역을 찾아야 합니다. 따라서 r1에 r3이 포함되도록 r1, r2 및 r3이 있는 경우 r2에 r3이 포함되는 r2가 없다는 것이 보장됩니다. 따라서 입력이 [["지구","북아메리카","남아메리카"], ["북아메리카","미국","캐나다"], ["미국","뉴욕", "Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]] 및 r1 ='Quebec' 및 r2 ='New York'인 경우 출력은 다음과 같습니다. '북미'

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 부모라는 지도 만들기
• 0에서 r
  크기 범위의 i에 대해
  • 범위 1에서 r[i]
    까지의 j에 대해
    • 부모[r[i, j]] :=r[i, 0]
• chain이라는 하나의 집합을 만들고 x를 chain에 삽입
• 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