Cây con kích thước chẵn trong cây n-ary trong C++

Cho danh sách kề biểu diễn cây n-ary. Nhiệm vụ: tìm số cây con có kích thước chẵn.

Cây n-ary: Nút gốc, mỗi nút giữ danh sách con trỏ đến nút con (số con <= m).

Ví dụ:

Đầu vào:

Đầu ra: 4

Giải thích: Cây con gốc tại 7, 2, 0, 3 có kích thước chẵn.

Phương pháp giải

Dùng DFS tính kích thước cây con cho mỗi nút. Nếu kích thước chẵn => tăng đếm. Một lần duyệt O(n).

Chương trình minh họa

Ví dụ

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

int countEventSizeSubTree(vector<int> adj[], int n, int v, int& EvenCount) {
    int size = 1;
    for (auto ele : adj[v]) {
        size += countEventSizeSubTree(adj, n, ele, EvenCount);
    }
    if (size % 2 == 0)
        EvenCount++;
    return size;
}

int main() {
    int n = 10;
    vector<int> adj[n + 1];
    adj[7].push_back(2);
    adj[7].push_back(9);
    adj[2].push_back(0);
    adj[2].push_back(1);
    adj[9].push_back(3);
    adj[3].push_back(8);
    adj[0].push_back(5);
    int EvenCount = 0;
    countEventSizeSubTree(adj, n, 1, EvenCount);
    cout << "Even Size SubTree are " << EvenCount;
    return 0;
}

Kết quả

Even Size SubTree are 0