Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में दी गई टिकटों की सूची से यात्रा कार्यक्रम खोजें


मान लीजिए हमारे पास प्रस्थान और आगमन हवाई अड्डों के जोड़े द्वारा दर्शाए गए टिकटों की एक सूची है जैसे [from, to], हमें क्रम में यात्रा कार्यक्रम ढूंढना है। सभी टिकट एक आदमी के हैं जो चेन्नई से प्रस्थान करता है। इसलिए, यात्रा कार्यक्रम चेन्नई से शुरू होना चाहिए।

तो यदि इनपुट [["Mumbai", " Kolkata"], ["Chennai ", " Mumbai"], ["Delhi", "Bangalore"], ["Kolkata", " Delhi"]] जैसा है, तो आउटपुट ["Chennai", " Mumbai", " Kolkata", " Delhi", "Bangalore"] होगा।

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

  • ret नामक एक सरणी और graph नामक एक मैप परिभाषित करें।

  • visit नामक एक विधि परिभाषित करें। यह हवाई अड्डे का नाम इनपुट के रूप में लेगा

  • जब तक graph[airport] का आकार 0 नहीं है

    • x := graph[airport] का पहला तत्व

    • graph[airport] से पहला तत्व हटाएं

    • visit(x) कॉल करें

  • airport को ret में डालें

  • अब मुख्य विधि से, निम्नलिखित करें −

  • i को 0 से टिकट सरणी के आकार तक की रेंज में

    • u := tickets[i, 0], v := tickets[i, 1], v को graph[u] में डालें

  • visit("Chennai") कॉल करें क्योंकि यह पहला हवाई अड्डा है

  • ret सूची को उल्टा करें और लौटाएं

उदाहरण (C++)

बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें −

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution {    public:    vector <string> ret;    map < string, multiset <string> > graph;    vector<string> findItinerary(vector<vector<string>>& tickets) {       for(int i = 0; i < tickets.size(); i++){          string u = tickets[i][0];          string v = tickets[i][1];          graph[u].insert(v);       }       visit("Chennai");       reverse(ret.begin(), ret.end());       return ret;    }    void visit(string airport){       while(graph[airport].size()){          string x = *(graph[airport].begin());          graph[airport].erase(graph[airport].begin());          visit(x);       }       ret.push_back(airport);    } }; main(){    Solution ob;    vector<vector<string>> v = {{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}};    print_vector(ob.findItinerary(v)); }

इनपुट

{{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}}

आउटपुट

[Chennai, Mumbai, Kolkata, Delhi, Bangalore, ]

  1. C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें

    यूक्लिडियन प्लेन ज्यामिति में एक चतुर्भुज चार शीर्षों और चार किनारों के साथ एक बहुभुज बनाता है। नाम 4-gon आदि। चतुर्भुजों के अन्य नामों में शामिल हैं और कभी-कभी उन्हें वर्ग, डिस्प्ले स्टाइल आदि के रूप में भी जाना जाता है।इस लेख में, हम दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करने के दृष

  1. बाइनरी ट्री में रूट से दिए गए नोड तक की दूरी खोजें C++ में बाइनरी ट्री में रूट से दिए गए नोड तक की दूरी खोजें C++ में

    मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें रूट और दूसरे नोड u के बीच की दूरी खोजनी है। मान लीजिए ट्री नीचे जैसा है: अब (रूट, 6) के बीच की दूरी = 2, पथ की लंबाई 2 है, (रूट, 8) के बीच की दूरी = 3 आदि। इस समस्या को हल करने के लिए, हम नोड को बाएं और दाएं सबट्री में खोजने के लिए एक पुन

  1. - पायथन में दी गई लिंक्ड लिस्ट से फोल्डेड लिस्ट खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक लिंक्ड लिस्ट है। हमें लिंक्ड लिस्ट का पहला आधा भाग लेना है और इसे दूसरे आधे भाग पर फोल्ड करना है फिर प्रतिच्छेदी नोड्स को उनके योग लेकर मर्ज करना है। अंत में, हमें परिणामी लिंक्ड लिस्ट का हेड लौटाना है।उदाहरण के लिए, यदि इनपुट [5,8,1,2,4,7,5] है, तो आउटपुट [2, 5, 15, 10] होगा।