fork(4) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. class TreeNode{
  8. public:
  9.     int num;
  10.     TreeNode *parent;
  11.     TreeNode *pair; ////node that appear in pair
  12.     vector<TreeNode*>childList;
  13.     TreeNode(int N){
  14.         num = N;
  15.         parent = nullptr;
  16.         pair = nullptr;
  17.     }
  18. };
  19.  
  20. class Tree{
  21. public:
  22.     int node_num;
  23.     TreeNode *root;
  24.     vector<TreeNode*> nodeList;
  25.     vector<TreeNode*> unconnectList; ////nodes that are not in the tree
  26.     Tree(int N, TreeNode *node){
  27.         node_num = N;
  28.         root = node;
  29.     }
  30.     bool Contain(int num){
  31.         for(auto & element: nodeList){
  32.             if(num == element->num){
  33.                 return true;
  34.             }
  35.         }
  36.         return false;
  37.     }
  38.     TreeNode* Find(int num){
  39.         for(auto & element: nodeList){
  40.             if(num == element->num){
  41.                 return element;
  42.             }
  43.         }
  44.         return nullptr;
  45.     }
  46. };
  47.  
  48. void SelectionSort(vector<TreeNode*>& array){
  49.     for(int i = 0; i < array.size() - 1; i++){
  50.         int min = i;
  51.         for(int j = i + 1; j < array.size(); j++){
  52.             if(array[j]->num < array[min]->num)
  53.                 min = j;
  54.         }
  55.         swap(array[i], array[min]);
  56.     }
  57. }
  58.  
  59. int BFS(TreeNode* root){
  60.     int last_num = 0;
  61.     queue<TreeNode*>q;
  62.     vector<TreeNode*>v; ////level order list
  63.  
  64.     q.push(root);
  65.     while(!q.empty()){
  66.         TreeNode* u= q.front();
  67.         v.push_back(u);
  68.         vector<TreeNode*> children = u->childList;
  69.         if(!children.empty()){
  70.             SelectionSort(children);
  71.         }
  72.         for(auto & node: children){
  73.             q.push(node);
  74.         }
  75.         q.pop();
  76.     }
  77.     last_num = v.back()->num;
  78.     return last_num;
  79.  
  80.  
  81. }
  82.  
  83. int main() {
  84.     int sum = 0;
  85.     int T;
  86.     cin>>T;
  87.     for(int i = 0; i < T; i++){
  88.         int N; ////total N nodes
  89.         int R; ////Root number
  90.         cin>>N>>R;
  91.         TreeNode *root = new TreeNode(R);
  92.  
  93.         Tree *T = new Tree (N, root);
  94.         T->nodeList.push_back(root);
  95.  
  96.         for(int j = 0; j < N-1; j++){
  97.             int num1;
  98.             int num2;
  99.             cin>>num1>>num2;
  100.             ////node1 has already in the tree, node2 not
  101.             ////node1 is parent, add node2 to its child list
  102.             if(T->Contain(num1) && !T->Contain(num2)){
  103.                 TreeNode *node2 = new TreeNode(num2);
  104.                 T->Find(num1)->childList.push_back(node2);
  105.                 node2->parent = T->Find(num1);
  106.                 T->nodeList.push_back(node2);
  107.             }
  108.             else if(!T->Contain(num1) && T->Contain(num2)){
  109.                 TreeNode *node1 = new TreeNode(num1);
  110.                 T->Find(num2)->childList.push_back(node1);
  111.                 node1->parent = T->Find(num2);
  112.                 T->nodeList.push_back(node1);
  113.             }
  114.             else if(!T->Contain(num1) && !T->Contain(num2)){
  115.                 TreeNode *node1 = new TreeNode(num1);
  116.                 TreeNode *node2 = new TreeNode(num2);
  117.                 T->unconnectList.push_back(node1);
  118.                 T->unconnectList.push_back(node2);
  119.                 node1->pair = node2;
  120.                 node2->pair = node1;
  121.             }
  122.         }
  123.  
  124.         ////add unconnected nodes to the tree
  125.         for(auto &node: T->unconnectList){
  126.             if(T->Contain(node->num) && !T->Contain(node->pair->num)){
  127.                 T->Find(node->num)->childList.push_back(node->pair);
  128.                 node->pair->parent = T->Find(node->num);
  129.                 T->nodeList.push_back(node->pair);
  130.             }
  131.         }
  132.         sum = sum + BFS(root);
  133.     }
  134.     cout<<sum<<endl;
  135.     return 0;
  136. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin 
1                                                                               
8 3                                                                             
2 4                                                                             
1 6                                                                             
1 8                                                                             
1 3                                                                             
3 2                                                                             
3 5                                                                             
7 2
stdout 
7
https://ideone.com/UjRIAi
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!