ภูมิภาคทั่วไปที่เล็กที่สุดใน C++

สมมติว่าเรามีรายชื่อภูมิภาคบางรายการซึ่งภูมิภาคแรกของแต่ละรายการรวมภูมิภาคอื่นๆ ทั้งหมดไว้ในรายการนั้น โดยพื้นฐานแล้วหากภูมิภาค X มีขอบเขต Y อื่น X จะมากกว่า Y และตามคำจำกัดความภูมิภาค X จะมีตัวมันเอง ถ้าเรามีสองภาค r1 และ r2, เราต้องหาพื้นที่ที่เล็กที่สุดที่มีทั้งคู่ ดังนั้นถ้าเรามี r1, r2 และ r3 ที่ r1 รวม r3 ก็รับประกันได้ว่าไม่มี r2 ที่ r2 รวม r3 ดังนั้น ถ้าอินพุตเป็นเหมือน [["Earth","อเมริกาเหนือ","South America"], ["North America","United States","Canada"], ["United States","New York", "บอสตัน"],["แคนาดา","ออนแทรีโอ","ควิเบก"],["อเมริกาใต้","บราซิล"]] และ r1 ='ควิเบก' และ r2 ='นิวยอร์ก' จากนั้นผลลัพธ์จะเป็น 'อเมริกาเหนือ'

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างแผนที่ชื่อพาเรนต์
• สำหรับ i ในช่วง 0 ถึงขนาด r
  • สำหรับ j ในช่วง 1 ถึงขนาดของ r[i]
    • พาเรนต์[r[i, j]] :=r[i, 0]
• สร้างชุดที่เรียกว่า chain และใส่ x ลงใน chain
• ในขณะที่ 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