หาจำนวนรอบขั้นต่ำจับคู่ได้ใน Tree (C++)

บทนำ

ในบทช่วยสอนนี้ เราจะหา จำนวนรอบ (rounds) ขั้นต่ำ ที่เราต้องใช้เพื่อจับคู่ (catch) คู่แข่งในต้นไม้ (Tree)

กฎของเกม

• Tree: กราฟไม่มีวงจร ไม่มีทิศทาง
• เราอยู่โหนด x, คู่แข่งอยู่โหนด y
• สลับกันเดิน: เราเดินก่อน แล้วคู่แข่งเดิน สลับกันไปเรื่อยๆ
• คู่แข่งสามารถ เลือกไม่เดิน (stay) ได้
• เราจับคู่ได้เมื่ออยู่โหนดเดียวกัน

ตัวอย่าง

Edges: [[0,1],[0,2],[1,3],[1,4]], x=0, y=3
Output: 3
Round 1: เรา 0→1, คู่แข่งอยู่ 3
Round 2: เรา 1→3, คู่แข่งอยู่ 3 → จับได้! (แต่ output คือ 3?)

หมายเหตุ: โค้ดคืนค่า 2×distance - 1 เพราะนับ "รอบ" แบบสลับกัน เราเดินรอบแรก คู่แข่งรอบที่สอง ฯลฯ

อัลกอริทึม: 2-Phase BFS

1. Phase 1: BFS จาก x (ตำแหน่งเรา) หา distance ไปทุกโหนด → array visited[]
2. Phase 2: BFS จาก y (ตำแหน่งคู่แข่ง) พร้อมเงื่อนไข:
   • คู่แข่งเดินได้ก็ต่อเมื่อ visited2[node] + 2 < visited[node]
   • หมายถึง: คู่แข่งต้องไปถึงโหนดก่อนที่เราจะไปถึง (คูณ 2 เพราะสลับรอบ)
   • อัปเดตคำตอบ: ret = max(ret, 2 * visited[node] - 1)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int visited[N];
int visited2[N];
vector graph[N];

class Solution {
public:
    int solve(vector>& 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();
        
        // สร้าง adjacency list
        for (auto& it : edges) {
            graph[it[0]].push_back(it[1]);
            graph[it[1]].push_back(it[0]);
        }
        
        // Phase 1: BFS จากเรา (u)
        queue 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);
                }
            }
        }
        
        // Phase 2: BFS จากคู่แข่ง (v)
        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>& edges, int u, int v) {
    return (new Solution())->solve(edges, u, v);
}

int main() {
    vector> edge = {{0,1},{0,2},{1,3},{1,4}};
    int x = 0, y = 3;
    cout << solve(edge, x, y);
    return 0;
}

ผลลัพธ์

3

คำอธิบาย

Distance(0,3) = 2 (0→1→3)
เราเดิน: รอบ1: 0→1, รอบ3: 1→3 → จับได้ที่รอบที่ 3
สูตร: 2×distance - 1 = 2×2 - 1 = 3

สรุป

Two-phase BFS หาจำนวนรอบขั้นต่ำจับคู่ใน Tree คู่แข่งหนีได้ต่อเมื่อไปถึงโหนดก่อนเรา (visited2+2 < visited) หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ