資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
