C++ में बस रूट्स (Bus Routes) समस्या

मान लीजिए हमारे पास बस रूट्स की एक सूची है। प्रत्येक routes[i] में एक बस रूट होता है जिसे i-वीं बस हमेशा दोहराती है। तो, यदि routes[0] = [1, 5, 7], इसका मतलब है कि पहली बस (0-थ इंडेक्स्ड) 1, 5, 7, 1, 5, 7, 1, ... के क्रम में हमेशा यात्रा करती है।

अब मान लीजिए हम बस स्टॉप S पर शुरू करते हैं, शुरू में बस पर नहीं, और हम बस स्टॉप T पर जाना चाहते हैं। हमें अपने गंतव्य तक पहुंचने के लिए कम से कम कितनी बसें लेनी होंगी? यदि यह संभव नहीं है तो -1 वापस करें।

तो यदि इनपुट [[1,2,8],[3,6,8]] जैसा है, और S = 1, T = 6, तो आउटपुट 2 होगा। तो, पहली बस से बस स्टॉप 7 तक जाएं, फिर दूसरी बस से बस स्टॉप 6 तक जाएं।

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

एक मैप m परिभाषित करें
i := 0 से प्रारंभ करें, जब i < r का आकार, i बढ़ाते हुए, करें -
- j := 0 से प्रारंभ करें, जब j < r[i] का आकार, j बढ़ाते हुए, करें -
  - m[r[i, j]] के अंत में i डालें
एक क्यू q परिभाषित करें, S को q में डालें
यदि S, T के समान है, तो -
- 0 वापस करें
एक सेट visited परिभाषित करें
lvl := 1 से प्रारंभ करें, जब q खाली नहीं है, lvl बढ़ाते हुए, करें -
- sz := q का आकार
- जब sz शून्येतर है, करें -
  - node := q का पहला तत्व, q से तत्व हटाएं
  - i := 0 से प्रारंभ करें, जब i < m[node] का आकार, i बढ़ाते हुए, करें -
    - route := m[node, i]
    - यदि route visited में है, तो -
      - अगले भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
    - route को visited में डालें
    - j := 0 से प्रारंभ करें, जब j < r[route] का आकार, j बढ़ाते हुए, करें -
      - stop := r[route, j]
      - यदि stop, T के समान है, तो -
        lvl वापस करें
    - stop को q में डालें
  - sz को 1 से घटाएं
-1 वापस करें

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

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution { public:    int numBusesToDestination(vector<vector<int>>& r, int S, int T) {       unordered_map <int, vector <int> > m;       for(int i = 0; i < r.size(); i++){          for(int j = 0; j < r[i].size(); j++){             m[r[i][j]].push_back(i);          }       }       queue <int> q;       q.push(S);       if(S == T) return 0;       unordered_set <int> visited;       for(int lvl = 1; !q.empty(); lvl++){          int sz = q.size();          while(sz--){             int node = q.front();             q.pop();             for(int i = 0; i < m[node].size(); i++){                int route = m[node][i];                if(visited.count(route)) continue;                visited.insert(route);                for(int j = 0; j < r[route].size(); j++){                   int stop = r[route][j];                   if(stop == T) return lvl;                   q.push(stop);                }             }          }       }       return -1;    } }; main(){    Solution ob;    vector<vector<int>> v = {{1,2,8}, {3,6,8}};    cout << (ob.numBusesToDestination(v, 1, 6)); }

इनपुट

{{1,2,8}, {3,6,8}} 1 6