C++-এ সবচেয়ে ছোট সाझা অঞ্চল

কিছু অঞ্চলের তালিকা দেওয়া আছে, যেখানে প্রতিটি তালিকার প্রথম অঞ্চল বাকি সব অঞ্চলকে অন্তর্ভুক্ত করে। অর্থাৎ, যদি অঞ্চল X অন্য অঞ্চল Y-কে অন্তর্ভুক্ত করে, তবে X, Y-থেকে বড়। একটি অঞ্চল নিজেকেও অন্তর্ভুক্ত করে বলে মনে করা হয়। দুটি অঞ্চল r1 আর r2 দেওয়া থাকলে, উভয়কেই অন্তর্ভুক্ত করে এমন সবচেয়ে ছোট অঞ্চলটি খুঁজে বের করতে হবে।

উদাহরণস্বরূপ, ইনপुट: [["Earth","North America","South America"], ["North America","United States","Canada"], ["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]], এবং r1 = 'Quebec', r2 = 'New York' হলে আউটপুট হবে 'North America'।

সমাধানের ধাপগুলো:

• parent নামের একটি ম্যাপ তৈরি করুন।
• i = 0 থেকে r.size()-1 পর্যন্ত:
  • j = 1 থেকে r[i].size()-1 পর্যন্ত: parent[r[i][j]] := r[i][0]
• chain নামের একটি সেট বানিয়ে x-কে ঢোকান।
• x যতক্ষণ parent-এ আছে:
  • x := parent[x]
  • chain-এ x ঢোকান
• y যতক্ষণ chain-এ নেই:
  • 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