परिचय
मान लीजिए हमारे पास ट्री एजेज की एक सूची है [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 पर चलते हैं।

समाधान दृष्टिकोण
- खिलाड़ी (x) से सभी नोड्स तक की दूरी की गणना करने के लिए BFS चलाएं।
- प्रतिद्वंद्वी (y) से BFS चलाएं, लेकिन केवल उन नोड्स पर जाएं जहां प्रतिद्वंद्वी खिलाड़ी से पहले पहुंच सकता है (visited2[node] + 2 < visited[node])।
- उत्तर 2 × max(visited[node]) - 1 है जहां प्रतिद्वंद्वी पहुंच सकता है।
उदाहरण कोड
#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);
return 0;
}
इनपुट
[[0, 1], [0, 2], [1, 3], [1, 4]], 0, 3
आउटपुट
3
निष्कर्ष
यह ट्री पर पीछा करने वाला खेल (pursuit-evasion game) है। खिलाड़ी प्रतिद्वंद्वी से दोगुनी गति से चलता है (प्रतिद्वंद्वी रुक सकता है)। इष्टतम रणनीति प्रतिद्वंद्वी के "सुरक्षित क्षेत्र" में सबसे दूर के नोड तक पहुंचना है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।