C++ में सबसे छोटा सामान्य क्षेत्र

मान लीजिए कि हमारे पास उन क्षेत्रों की कुछ सूचियाँ हैं जहाँ प्रत्येक सूची के पहले क्षेत्र में उस सूची के अन्य सभी क्षेत्र शामिल हैं। मूल रूप से, यदि एक क्षेत्र X में कोई अन्य क्षेत्र Y है, तो X, Y से बड़ा है। साथ ही परिभाषा के अनुसार एक क्षेत्र X में स्वयं शामिल है। इसलिए यदि हमारे पास दो क्षेत्र r1 और r2 हैं, तो हमें उन दोनों को शामिल करने वाला सबसे छोटा क्षेत्र खोजना होगा। तो अगर हमारे पास r1, r2 और r3 है जैसे कि r1 में r3 शामिल है, तो यह गारंटी है कि कोई r2 नहीं है जैसे कि r2 में r3 शामिल है। तो अगर इनपुट [["पृथ्वी", "उत्तरी अमेरिका", "दक्षिण अमेरिका"], ["उत्तरी अमेरिका", "संयुक्त राज्य", "कनाडा"], ["संयुक्त राज्य अमेरिका", "न्यूयॉर्क", "बोस्टन"], ["कनाडा", "ओंटारियो", "क्यूबेक"], ["दक्षिण अमेरिका", "ब्राज़ील"]], और r1 ='क्यूबेक' और r2 ='न्यूयॉर्क', तो आउटपुट होगा 'उत्तरी अमेरिका'

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• पेरेंट नामक नक्शा बनाएं
• i के लिए 0 से r के आकार की सीमा में
  • जे के लिए 1 से लेकर r के आकार तक[i]
    • अभिभावक[r[i, j]] :=r[i, 0]
• चेन नामक एक सेट बनाएं, और 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