fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <assert.h>
  5. #include <string.h>
  6. #include <string>
  7.  
  8. #define MAX 55
  9.  
  10. using namespace std;
  11.  
  12. vector<vector<int>> children;
  13. vector<int> parentVec;
  14. int leaf_num = 0;
  15.  
  16. void deleteNode(int root) //해당 노드를 root로 가지는 subtree의 리프 노드 수만큼 leaf_node--
  17. {
  18.     if (children[root].size() == 0) //지울 노드가 리프 노드면 leaf_num--;
  19.     {
  20.         leaf_num--;
  21.         return;
  22.     }
  23.     for (auto child : children[root]) //리프 노드가 아니면 자식들 삭제
  24.         deleteNode(child);
  25. }
  26.  
  27. int main()
  28. {
  29.     ////////////////////input////////////////////
  30.     cin.tie(NULL);
  31.     ios_base::sync_with_stdio(false);
  32.     int n, parent, root = -1, toDelete;
  33.     cin >> n;
  34.     children.resize(n);
  35.     parentVec.resize(n);
  36.     for (int i = 0; i < n; i++)
  37.     {
  38.         cin >> parent;
  39.         parentVec.push_back(parent);
  40.         if (parent != -1)
  41.             children[parent].push_back(i);
  42.         else
  43.             root = i;
  44.     }
  45.     assert(root != -1);
  46.     cin >> toDelete;
  47.  
  48.     if (toDelete == root) //root를 지우는 경우
  49.     {
  50.         cout << 0;
  51.         return 0;
  52.     }
  53.  
  54.     for (auto childrenVector : children)
  55.     {
  56.         if (childrenVector.size() == 0)
  57.             leaf_num++;
  58.     }
  59.     deleteNode(toDelete);
  60.     if (children[parentVec[toDelete]].size() == 1)
  61.         leaf_num++;
  62.  
  63.     ////////////////////output///////////////////
  64.     cout << leaf_num;
  65.  
  66.     return 0;
  67. }
  68.  
  69. /*legacy
  70.  
  71.  
  72.  
  73. */
Success #stdin #stdout 0s 4312KB
comments (?)
stdin
copy 
4
-1 0 0 1
3
stdout
copy 
1
https://ideone.com/lBAUFg
language:
C++14 (gcc 8.3)
created:
3 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!