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

मान लीजिए हमारे पास क्षेत्रों की कुछ सूचियाँ हैं जहां प्रत्येक सूची का पहला क्षेत्र उस सूची के अन्य सभी क्षेत्रों को शामिल करता है। मूल रूप से, यदि क्षेत्र X में क्षेत्र Y है, तो X, Y से बड़ा है। परिभाषा के अनुसार एक क्षेत्र X स्वयं को भी शामिल करता है। यदि हमारे पास दो क्षेत्र r1 और r2 हैं, तो हमें सबसे छोटा क्षेत्र ढूंढना है जो उन दोनों को शामिल करता है। यदि हमारे पास r1, r2 और r3 हैं जैसे कि r1 में r3 शामिल है, तो यह गारंटी है कि कोई r2 नहीं है जो r3 को शामिल करता हो।

उदाहरण के लिए, यदि इनपुट [["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 के आकार तक लूप करें
  • j को 1 से r[i] के आकार तक लूप करें
    • parent[r[i, j]] := r[i, 0]
• chain नामक एक सेट बनाएं, और x को chain में डालें
• जब तक x parent में है:
  • x := parent[x]
  • x को chain में डालें
• जब तक 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