C++で対戦相手を捕まえるために必要な最小ステップ数を見つけるためのプログラム

[u、v]の形式のツリーエッジのリストがあると仮定します。これは、uとvの間に無向エッジがあることを示します。また、xとyの2つの値があります。ノード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ノードの隣接リストグラフを作成する

• エッジリストの各エッジについて、実行します

  • グラフの最後にit[v]を挿入します[it[u]]

  • グラフの最後にit[u]を挿入します[it[v]]

• 1つのキューを定義しますw

• uをqに挿入

• 訪問済み[u]：=0

• qが空でないときに、-

  を実行します。

  • node：=qの最初の要素

  • qから要素を削除

  • 各ノードについて、graph [node]

    にあります

    • visited [it]が-1と同じ場合、-

      • 訪問済み[it]：=訪問済み[ノード] + 1

      • qに挿入

• vをqに挿入

• ret：=0

• visited2 [v]：=0

• qが空でない間）、実行-

  • node：=qの最初の要素

  • qから要素を削除

  • ret：=retの最大値と2*（visited [node]）

  • 各ノードについて、graph [node]

    にあります

    • visited2[it]が-1およびvisited2[node]+ 2

      • 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

出力

3