แปลงต้นไม้เป็นฟอเรสต์ของโหนดคู่ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลงทรีเป็นฟอเรสต์ที่มีโหนดเท่ากัน

สำหรับสิ่งนี้ เราจะได้รับไบนารีทรีของโหนด N ที่กล่าว งานของเราคือการคำนวณจำนวนขอบสูงสุดที่สามารถลบออกเพื่อให้ได้ฟอเรสต์ของโหนดคู่

ตัวอย่าง

#include<bits/stdc++.h>
#define N 12
using namespace std;
//returning the number of nodes of subtree
//having the root node
int depth_search(vector<int> tree[N], int visit[N], int *ans, int node){
   int num = 0, temp = 0;
   //marking nodes as visited
   visit[node] = 1;
   for (int i = 0; i < tree[node].size(); i++){
      if (visit[tree[node][i]] == 0){
      //finding total nodes of the sub subtree
      temp = depth_search(tree, visit, ans, tree[node][i]);
      //if nodes are even, increment the edges to be removed by 1
      (temp%2)?(num += temp):((*ans)++);
      }
   }
   return num+1;
}
//returning the maximum number of edges to be removed
int print_maxedge(vector<int> 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<int> 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