C++ में सभी रास्तों को सिटी जीरो की ओर ले जाने के लिए रूटों को फिर से क्रमित करें

मान लीजिए कि n अलग-अलग शहर हैं जिनकी संख्या 0 से n-1 तक है और n-1 सड़कें भी हैं जैसे कि दो अलग-अलग शहरों के बीच यात्रा करने का केवल एक ही रास्ता है। मान लीजिए परिवहन मंत्रालय ने सड़कों को एक दिशा में उन्मुख करने का फैसला किया क्योंकि वे बहुत संकरी हैं।

यहां सड़कों को कनेक्शन द्वारा दर्शाया जाता है जहां कनेक्शन [i] =[ए, बी] यह शहर ए से बी तक की सड़क का प्रतिनिधित्व करता है।

यदि राजधानी में कोई बड़ा आयोजन होता है (शहर की संख्या 0), और बहुत से लोग इस शहर की यात्रा करना चाहते हैं। हमें कुछ सड़कों पर कुछ पुनर्रचना कार्य करना है जैसे कि प्रत्येक शहर 0 शहर की यात्रा कर सकता है। हमें किनारों की न्यूनतम संख्या को बदलना होगा।

इसलिए, यदि इनपुट 6 की तरह है, तो कनेक्शन =[[0,1], [1,3], [2,3], [4,0], [4,5]],

तो आउटपुट 3 होगा, क्योंकि हमें किनारों की दिशा लाल रंग में बदलनी होगी ताकि प्रत्येक नोड राजधानी तक पहुंच सके।

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

• सूचियों की दो सरणी परिभाषित करें ग्राफ़1, ग्राफ़2 आकार N =5*10^4 + 5

• मुख्य विधि से निम्न कार्य करें -

• एक मानचित्र को इसमें परिभाषित करें

• ई में प्रत्येक तत्व के लिए, करें

  • इसे [1] ग्राफ़ 1 के अंत में डालें [यह [0]]

  • इसे [0] ग्राफ़2 के अंत में डालें[it[1]]

• आकार n की एक सरणी को परिभाषित करें और इसे N + 10 से भरें

• रिट:=0, [0] में:=0, जिला [0]:=0

• एक कतार को परिभाषित करें q

• q में 0 डालें

• देखे गए एक सेट को परिभाषित करें

• विज़िट किए गए में 0 डालें

• जबकि (नहीं q खाली है), करें -

  • नोड:=q का पहला तत्व

  • q से तत्व हटाएं

  • रिट:=रिट + डिस्ट [नोड]

  • प्रत्येक तत्व के लिए इसे ग्राफ़ 2 [नोड] में, करें

    • अगर यह दौरा नहीं किया गया है और [यह]> 0, तो -

      • जिला [यह]:=0

      • इसे q में डालें

      • इसे विज़िट किए गए में डालें

  • प्रत्येक तत्व के लिए इसे ग्राफ़ 1 [नोड] में, करें

    • अगर यह दौरा नहीं किया जाता है और [यह]> 1 को दूर करता है, तो -

      • जिला [यह] :=1

      • इसे q में डालें

      • इसे विज़िट किए गए में डालें

• वापसी रिट

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
class Solution {
public:
   vector<int> graph1[N];
   vector<int> graph2[N];
   int minReorder(int n, vector<vector<int> >& e){
      map<int, int> in;
      for (auto& it : e) {
         graph1[it[0]].push_back(it[1]);
         graph2[it[1]].push_back(it[0]);
      }
      vector<int> dist(n, N + 10);
      int ret = 0;
      in[0] = 0;
      dist[0] = 0;
      queue<int> q;
      q.push(0);
      set<int> visited;
      visited.insert(0);
      while (!q.empty()) {
         int node = q.front();
         q.pop();
         ret += dist[node];
         for (auto& it : graph2[node]) {
            if (!visited.count(it) && dist[it] > 0) {
               dist[it] = 0;
               q.push(it);
               visited.insert(it);
            }
         }
         for (auto& it : graph1[node]) {
            if (!visited.count(it) && dist[it] > 1) {
               dist[it] = 1;
               q.push(it);
               visited.insert(it);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{1,3},{2,3},{4,0},{4,5}};
   cout << (ob.minReorder(6,v));
}

इनपुट

6,{{0,1},{1,3},{2,3},{4,0},{4,5}}

आउटपुट

3