C++ এ ক্ষুদ্রতম সাধারণ অঞ্চল

ধরুন আমাদের কাছে এমন কিছু অঞ্চলের তালিকা রয়েছে যেখানে প্রতিটি তালিকার প্রথম অঞ্চলটি সেই তালিকার অন্যান্য সমস্ত অঞ্চলকে অন্তর্ভুক্ত করে। মূলত, যদি একটি অঞ্চল X-এ অন্য একটি অঞ্চল Y থাকে, তাহলে X হল Y-এর থেকে বড়। এছাড়াও সংজ্ঞা অনুসারে একটি অঞ্চল X-এ নিজেকে ধারণ করে। তাই যদি আমাদের দুটি অঞ্চল r1 এবং r2 থাকে, তাহলে আমাদেরকে সেই ক্ষুদ্রতম অঞ্চলটি খুঁজে বের করতে হবে যেখানে উভয়ই রয়েছে। তাই যদি আমাদের কাছে r1, r2 এবং r3 থাকে যাতে r1-এ r3 অন্তর্ভুক্ত থাকে, তাহলে নিশ্চিত যে r2-এ r3 অন্তর্ভুক্ত থাকবে না। সুতরাং যদি ইনপুট হয় [["পৃথিবী","উত্তর আমেরিকা","দক্ষিণ আমেরিকা"], ["উত্তর আমেরিকা","মার্কিন যুক্তরাষ্ট্র","কানাডা"], ["মার্কিন যুক্তরাষ্ট্র","নিউ ইয়র্ক", "বোস্টন"],["কানাডা","অন্টারিও","কুইবেক"],["দক্ষিণ আমেরিকা","ব্রাজিল"]], এবং r1 ='কিউবেক' এবং r2 ='নিউ ইয়র্ক', তাহলে আউটপুট হবে 'উত্তর আমেরিকা'

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• অভিভাবক নামে একটি মানচিত্র তৈরি করুন
• আমি 0 থেকে r
  এর মাপের পরিসরে
  • j এর জন্য রেঞ্জ 1 থেকে r[i]
    এর আকার
    • পিতা[r[r[i, j]] :=r[i, 0]
• চেইন নামক একটি সেট তৈরি করুন এবং চেইনে x ঢোকান
• যখন x পিতামাতার মধ্যে থাকে,
  • x :=পিতামাতা[x]
  • চেইনে x ঢোকান
• যখন 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