数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 := 1^5 + 5
定义一个大小为 N 的数组 visited 和另一个大小为 N 的数组 visited2，并将它们都填充为 -1
为 N 个节点创建邻接表图
对于 edges 列表中的每个边 it，执行以下操作：
将 it[v] 插入到 graph[it[u]] 的末尾
将 it[u] 插入到 graph[it[v]] 的末尾
定义一个队列 w
将 u 插入到队列 q 中
visited[u] := 0
当队列 q 不为空时，执行以下操作：
node := 队列 q 的第一个元素
从队列 q 中删除元素
对于 graph[node] 中的每个节点 it
如果 visited[it] 等于 -1，则：
visited[it] := visited[node] + 1
将 it 插入到队列 q 中
将 v 插入到队列 q 中
ret := 0
visited2[v] := 0
当队列 q 不为空时，执行以下操作：
node := 队列 q 的第一个元素
从队列 q 中删除元素
ret := ret 和 2 * (visited[node]) 的最大值
对于 graph[node] 中的每个节点 it
如果 visited2[it] 等于 -1 且 visited2[node] + 2 < visited[it]，则：
visited2[it] := visited2[node] + 1
将 it 插入到队列 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
输出
3
156 次查看
