C++ में ट्री को सम नोड्स के फॉरेस्ट में बदलें

इस ट्यूटोरियल में, हम एक प्रोग्राम पर चर्चा करेंगे जो ट्री को सम नोड्स के फॉरेस्ट में बदलता है।

इसके लिए हमें N नोड्स का एक बाइनरी ट्री दिया जाएगा। हमारा कार्य हटाए जा सकने वाले अधिकतम एज की संख्या की गणना करना है ताकि सम नोड्स का फॉरेस्ट प्राप्त हो सके।

उदाहरण

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

//रूट नोड वाले सबट्री के नोड्स की संख्या लौटाना
int depth_search(vector tree[N], int visit[N], int* ans, int node) {
    int num = 0, temp = 0;
    //नोड्स को विजिटेड मार्क करना
    visit[node] = 1;
    
    for (int i = 0; i < tree[node].size(); i++) {
        if (visit[tree[node][i]] == 0) {
            //सब-सबट्री के कुल नोड्स ढूंढना
            temp = depth_search(tree, visit, ans, tree[node][i]);
            //यदि नोड्स सम हैं, तो हटाए जाने वाले एज को 1 से बढ़ाएं
            (temp % 2) ? (num += temp) : ((*ans)++);
        }
    }
    return num + 1;
}

//हटाए जाने वाले अधिकतम एज की संख्या लौटाना
int print_maxedge(vector tree[N], int n) {
    int visit[n + 2];
    int ans = 0;
    memset(visit, 0, sizeof visit);
    depth_search(tree, visit, &ans, 1);
    return ans;
}

int main() {
    int n = 10;
    vector tree[n + 2];
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[1].push_back(6);
    tree[6].push_back(1);
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[3].push_back(4);
    tree[4].push_back(3);
    tree[6].push_back(8);
    tree[8].push_back(6);
    tree[2].push_back(7);
    tree[7].push_back(2);
    tree[2].push_back(5);
    tree[5].push_back(2);
    tree[4].push_back(9);
    tree[9].push_back(4);
    tree[4].push_back(10);
    tree[10].push_back(4);
    cout << print_maxedge(tree, n) << endl;
    return 0;
}

आउटपुट

2