Chương trình C++ tìm người thắng trò chơi tô màu ô

Cho hai mảng A, B kích thước N. Có N ô và N-1 đường nối (cây). Ô 1 đen, ô N trắng. Amal (đen) và Bimal (trắng) luân phiên tô ô chưa tô liền kề màu của mình. Ai không tô được thì thua. Tìm người thắng.

Ví dụ

Với A=[3,1,3,7,5,1], B=[6,2,1,4,7,4], Amal thắng.

Giải thuật

DFS từ đỉnh 1 tính cha, độ sâu, kích thước cây con. Tìm đỉnh ở giữa đường đi 1→N (bước (d[N]-1)/2 từ N về cha). Nếu kích thước cây con của đỉnh đó 2*ssz >= N thì Bimal thắng, ngược lại Amal thắng.

Mã 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;
}

Đầu vào / Đầu ra

Input: { 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 }
Output: Amal