โปรแกรมหาจำนวนก้าวขั้นต่ำที่ต้องจับคู่ต่อสู้ใน C++

สมมติว่าเรามีรายการขอบต้นไม้ในรูปแบบ [u, v] ซึ่งบ่งชี้ว่ามีขอบที่ไม่มีทิศทางระหว่าง u และ v และเรายังมีค่า x และ y สองค่าอีกด้วย ถ้าเราอยู่ที่โหนด x และคู่ต่อสู้ของเราอยู่ที่โหนด y ในรอบแรก เราเคลื่อนที่ จากนั้นในรอบถัดไป ฝ่ายตรงข้ามจะเคลื่อนที่ไปเรื่อยๆ ฝ่ายตรงข้ามสามารถเลือกที่จะไม่ทำการย้ายในรอบ เราต้องหาจำนวนรอบขั้นต่ำที่ต้องจับคู่ต่อสู้ให้ได้

ดังนั้น หากอินพุตเป็นเหมือนขอบ =[[0, 1], [0, 2], [1, 3], [1, 4]], x =0, y =3 ผลลัพธ์จะเป็น 3 ในตอนแรก เราย้ายจากโหนด 0 ไปยัง 1 จากนั้นฝ่ายตรงข้ามจะอยู่ในโหนด 3 ปัจจุบัน จากนั้นเราจะย้ายไปที่โหนด 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=1^5 + 5

• กำหนดขนาดอาร์เรย์ที่เข้าชม:N และอีกอาร์เรย์ที่เข้าชม2 ขนาด:N เติมด้วย -1

• สร้างกราฟรายการที่อยู่ติดกันสำหรับโหนด N

• สำหรับแต่ละขอบในรายการขอบ ทำ

  • ใส่มัน[v] ที่ท้ายกราฟ[it[u]]

  • ใส่มัน[u] ที่ท้ายกราฟ[it[v]]

• กำหนดหนึ่งคิว w

• ใส่ u ลงใน q

• เยี่ยมชม[u] :=0

• ในขณะที่ q ไม่ว่างให้ทำ -

  • โหนด :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • สำหรับแต่ละโหนดในกราฟ[โหนด]

    • ถ้ามาเยี่ยม[มัน] ก็เหมือนกับ -1 แล้ว −

      • เยี่ยมชม[it] :=เยี่ยมชม[โหนด] + 1

      • แทรกลงใน q

• แทรก v ลงใน q

• ยกเลิก :=0

• เยี่ยมชม2[v] :=0

• ในขณะที่ q ไม่ว่าง) ให้ทำ -

  • โหนด :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • ret :=สูงสุดของ ret และ 2 * (เข้าชมแล้ว[โหนด])

  • สำหรับแต่ละโหนดในกราฟ[โหนด]

    • ถ้า visit2[it] เหมือนกับ -1 และ visit2[node] + 2

      • visit2[it] :=visit2[node] + 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