[u, v] 형식의 트리 가장자리 목록이 있다고 가정합니다. 이는 u와 v 사이에 무방향 가장자리가 있음을 나타냅니다. 그리고 x와 y 값도 두 개 있습니다. 우리가 노드 x에 있고 상대가 노드 y에 있는 경우. 첫 번째 라운드에서는 우리가 이동하고 다음 라운드에서는 상대방이 이동하는 식으로 진행됩니다. 상대방은 라운드에서 움직이지 않도록 선택할 수 있습니다. 상대를 잡는 데 필요한 최소 라운드 수를 찾아야 합니다.
따라서 입력이 edge =[[0, 1], [0, 2], [1, 3], [1, 4]], x =0, y =3과 같으면 출력은 3이 됩니다. 처음과 같이 노드 0에서 1로 이동합니다. 그러면 상대방은 현재 노드 3에 머물고 우리는 노드 3으로 이동합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N :=1^5 + 5
-
크기가 N인 방문 배열을 정의하고 크기가 N인 다른 방문2 배열을 정의합니다. −1
-
N 노드에 대한 인접 목록 그래프 생성
-
가장자리 목록의 각 가장자리에 대해
-
그래프 끝에[v] 삽입[it[u]]
-
그래프 끝에[u] 삽입[it[v]]
-
-
하나의 대기열 정의 w
-
u를 q에 삽입
-
방문[u] :=0
-
q가 비어 있지 않은 동안 수행 -
-
node :=q의 첫 번째 요소
-
q에서 요소 삭제
-
각 노드에 대해 그래프[노드]
-
방문[it]이 −1과 같으면 −
-
방문[it] :=방문[노드] + 1
-
q에 삽입
-
-
-
-
v를 q에 삽입
-
렛 :=0
-
방문2[v] :=0
-
q가 비어 있지 않은 동안) -
를 수행합니다.-
node :=q의 첫 번째 요소
-
q에서 요소 삭제
-
ret :=ret의 최대값 및 2 * (방문한[노드])
-
각 노드에 대해 그래프[노드]
-
방문2[it]이 -1 및 방문2[노드] + 2 <방문[it]과 같으면 -
-
방문2[it] :=방문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
출력
3