C++-এ প্রতিপক্ষকে ধরতে ন্যূনতম রাউন্ড সংখ্যা বের করা

মান লইয়া আমাদের একটি ট্রি এজ লিস্ট দেওয়া আছে [u, v] ফরম্যাটে, এটি নির্দেশ করে u এবং v-এর মধ্যে একটি অনডিরেক্টেড এজ আছে। এবং আমাদের দুটি ভ্যালু x এবং y আছে। আমরা নোড x-এ আছি, এবং আমাদের প্রতিপক্ষ নোড y-এ। প্রথম রাউন্ডে আমরা মুভ করব, তারপর পরবর্তী রাউন্ডে প্রতিপক্ষ মুভ করবে এবং এভাবে চলবে। প্রতিপক্ষ চাইলে একটি রাউন্ডে মুভ না করেও থাকতে পারে। আমাদের বের করতে হবে প্রতিপক্ষকে ধরতে ন্যূনতম কত রাউন্ড লাগবে।

তবে, যদি ইনপুট হয় edges = [[0, 1], [0, 2], [1, 3], [1, 4]], x = 0, y = 3, তবে আউটপুট হবে 3, কারণ প্রথমে আমরা নোড 0 থেকে 1-এ যাব। তারপর প্রতিপক্ষ বর্তমান নোড 3-এ থাকবে। তারপর আমরা নোড 3-এ যাব।

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:

N := 10^5 + 5
সাইজ N-এর visited এবং visited2 অ্যারে ডিফাইন করুন -1 দিয়ে ফিল্ড
N নোডের জন্য অ্যাডজেসেন্সি লিস্ট গ্রাফ তৈরি করুন
edges লিস্টের প্রতিটি edge için:
- graph[it[0]]-এ it[1] পুশ করুন
- graph[it[1]]-এ it[0] পুশ করুন
একটি কিউ q ডিফাইন করুন
u কে q-তে পুশ করুন
visited[u] := 0
q খালি না হলে:
- node := q-এর ফ্রন্ট
- q-তে পপ করুন
- graph[node]-এর প্রতিটি it জন্য:
  - যদি visited[it] == -1 হয়, visited[it] := visited[node] + 1 এবং q-তে পুশ করুন
v কে q-তে পুশ করুন
ret := 0
visited2[v] := 0
q খালি না হলে:
- node := q-এর ফ্রন্ট
- q-তে পপ করুন
- ret := max(ret, 2 * visited[node] - 1)
- graph[node]-এর প্রতিটি it জন্য:
  - যদি visited2[it] == -1 এবং visited2[node] + 2 < visited[it], তবে visited2[it] := visited2[node] + 1 এবং q-তে পুশ করুন
ret রিটার্ন করুন

বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

#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