सी ++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास [u, v] के रूप में पेड़ के किनारों की एक सूची है, यह इंगित करता है कि u और v के बीच एक अप्रत्यक्ष किनारा है। और हमारे पास दो मान x और y भी हैं। यदि हम नोड x पर हैं, और हमारा प्रतिद्वंद्वी नोड y पर है। पहले दौर में, हम आगे बढ़ते हैं, फिर अगले दौर में प्रतिद्वंद्वी चलता है और इसी तरह। प्रतिद्वंद्वी एक राउंड में कोई चाल नहीं चलने का चयन कर सकता है। हमें प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम राउंड की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट किनारों की तरह है =[[0, 1], [0, 2], [1, 3], [1, 4]], x =0, y =3, तो आउटपुट 3 होगा, पहले की तरह, हम नोड 0 से 1 की ओर बढ़ते हैं। फिर प्रतिद्वंद्वी वर्तमान नोड 3 में रहता है। फिर हम नोड 3 पर जाते हैं।

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

एन:=1^5 + 5
विज़िट किए गए आकार की एक सरणी को परिभाषित करें:N और दूसरी विज़िट की गई 2 आकार की सरणी:N उन्हें −1
. से भरें
एन नोड्स के लिए आसन्नता सूची ग्राफ बनाएं
किनारों की सूची में प्रत्येक किनारे के लिए, करें
- इसे [v] ग्राफ़ के अंत में डालें[it[u]]
- इसे [u] ग्राफ़ के अंत में डालें[it[v]]
एक कतार को परिभाषित करें w
आपको q में सम्मिलित करें
विज़िट किया गया[यू] :=0
जबकि q खाली नहीं है, करें -
- नोड:=q का पहला तत्व
- q से तत्व हटाएं
- प्रत्येक नोड के लिए इसे ग्राफ़ में [नोड]
  - यदि विज़िट किया गया [यह] -1 के समान है, तो -
    - विज़िट किया गया [यह] :=विज़िट किया गया [नोड] + 1
    - इसे q में डालें
q में v डालें
रिट:=0
विज़िट किया गया2[v] :=0
जबकि q खाली नहीं है), करें −
- नोड:=q का पहला तत्व
- q से तत्व हटाएं
- रिट :=अधिकतम रिट और 2 * (विज़िट [नोड])
- प्रत्येक नोड के लिए इसे ग्राफ़ में [नोड]
  - यदि विज़िट किया गया2[यह] -1 के समान है और विज़िट किया गया2[नोड] + 2 <विज़िट किया गया है [यह], तो -
    - विज़िट किया गया2[यह] :=विज़िट किया गया2[नोड] + 1
    - इसे q में डालें
वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int visited[N];
int visited2[N];
vector<int> graph[N];
class Solution {
   public:
   int solve(vector<vector<int>>& edges, int u, int v) {
      memset(visited, −1, sizeof visited);
      memset(visited2, −1, sizeof visited2);
      for (int i = 0; i < N; i++)
      graph[i].clear();
      for (auto& it : edges) {
         graph[it[0]].push_back(it[1]);
         graph[it[1]].push_back(it[0]);
      }
      queue<int> q;
      q.push(u);
      visited[u] = 0;
      while (!q.empty()) {
         int node = q.front();
         q.pop();
         for (auto& it : graph[node]) {
            if (visited[it] == −1) {
               visited[it] = visited[node] + 1;
               q.push(it);
            }
         }
      }
      q.push(v);
      int ret = 0;
      visited2[v] = 0;
      while (!q.empty()) {
         int node = q.front();
         q.pop();
         ret = max(ret, 2 * (visited[node]) − 1);
         for (auto& it : graph[node]) {
            if (visited2[it] == −1 && visited2[node] + 2 <
            visited[it]) {
               visited2[it] = visited2[node] + 1;
               q.push(it);
            }
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& edges, int u, int v) {
   return (new Solution())−>solve(edges, u, v);
}
int main(){
   vector<vector<int>> edge = {{0, 1},{0, 2},{1, 3},{1, 4}};
   int x = 0, y = 3;
   cout << solve(edge, x, y);
}

इनपुट

[
   [0, 1],
   [0, 2],
   [1, 3],
   [1, 4]
], 0, 3