โปรแกรม C++ หาผู้ชนะเกมทาสีเซลล์บนกราฟ

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A และ B ทั้งคู่ N องค์ประกอบ พิจารณาเกมบนกระดานเซลล์ 1 ถึง N มีถนน N-1 เส้น เนื่องจากเส้นที่ i เชื่อม A[i] กับ B[i] ทุกเซลล์เข้าถึงกันได้ เริ่มต้นเซลล์ 1 สีดำ เซลล์ N สีขาว อื่นๆ ไม่มีสี อมลเล่นก่อน สลับกันเล่น อมลเลือกเซลล์ว่างติดเซลล์ดำ ทาสีดำ บีม่าลเลือกเซลล์ว่างติดเซลล์ขาว ทาสีขาว คนที่ทาไม่ได้แพ้ ต้องการหาผู้ชนะ

ตัวอย่าง: A = [3, 1, 3, 7, 5, 1]; B = [6, 2, 1, 4, 7, 4] ผลลัพธ์คือ Amal เพราะถ้าอมลทาเซลล์ 2 สีดำก่อน จะชนะไม่ว่าบีม่าจะเล่นอย่างไร

ขั้นตอนการแก้ปัญหา

N := 99999
กำหนด adjacency list adjList
กำหนดอาร์เรย์ p, d, ssz ขนาดใหญ่
ฟังก์ชัน dfs(nd, par, dep):
    p[nd] := par
    d[nd] := dep
    ssz[nd] := 1
    สำหรับ i ใน adjList[nd]:
        ถ้า i XOR par ไม่เป็นศูนย์:
            dfs(i, nd, dep + 1)
            ssz[nd] := ssz[nd] + ssz[i]
จาก main:
    n := ขนาดของ A
    สำหรับ i := 1 ถึง n-1:
        u := A[i-1], v := B[i-1]
        ใส่ v ลง adjList[u], ใส่ u ลง adjList[v]
    dfs(1, 1, 0)
    nd := n
    สำหรับ i := 0 ถึง (d[n]-1)/2 - 1:
        nd := p[nd]
    คืนค่า "Bimal" ถ้า 2*ssz[nd] >= n มิฉะนั้น "Amal"

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

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

int N = 99999;
vector<vector<int>> adjList(N);
vector<int> p(N), d(N), ssz(N);

void dfs(int nd, int par, int dep){
    p[nd] = par;
    d[nd] = dep;
    ssz[nd] = 1;
    for (int i : adjList[nd]){
        if (i ^ par){
            dfs(i, nd, dep + 1);
            ssz[nd] += ssz[i];
        }
    }
}

string solve(vector<int> A, vector<int> B){
    int n = A.size();
    for (int i = 1; i < n; i++){
        int u = A[i - 1], v = B[i - 1];
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    dfs(1, 1, 0);
    int nd = n;
    for (int i = 0; i < (d[n] - 1) / 2; i++)
        nd = p[nd];
    return (2 * ssz[nd] >= n ? "Bimal" : "Amal");
}

int main(){
    vector<int> A = { 3, 1, 3, 7, 5, 1 };
    vector<int> B = { 6, 2, 1, 4, 7, 4 };
    cout << solve(A, B) << endl;
}

อินพุต

{ 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 }

เอาต์พุต

Amal