#include #include #include #include using namespace std; class Node{ public: int value; bool is_leaf = true; Node* left = nullptr; Node* right = nullptr; Node* parent = nullptr; Node(int a) : value(a), is_leaf(true), left(nullptr), right(nullptr) {}; ~Node(); }; class Graph{ public: Node* root = nullptr; int vertices = 0; Graph(int a) { root = new Node(a); } Node* traverse(Node* current, int value) { if (current == nullptr) return nullptr; if (current->value == value) return current; Node* found = traverse(current->left, value); if (found) return found; return traverse(current->right, value); } void insert(int value, int parent) { Node* parents = traverse(root, parent); Node* now = new Node(value); now->parent = parents; if (parents->left == nullptr) parents->left = now; else if (parents->right == nullptr) parents->right = now; parents->is_leaf = false; vertices += 1; } void remove(int value, int parent) { Node* parents = traverse(root, parent); bool is_left = 0; if (parents->left->value == value) is_left = 1; if (is_left) { parents->left = nullptr; } else { parents->right = nullptr; } if (parents->left == nullptr && parents->right == nullptr) { parents->is_leaf = true; } vertices -= 1; } void find_leaf(Node* current, int *value) { if (current != nullptr) { if (current->is_leaf == true) *value += 1; find_leaf(current->left, value); find_leaf(current->right, value); } } }; int main() { int N; cin >> N; vector parents(N); Graph* graph = nullptr; for (int i = 0; i < N; i++) cin >> parents[i]; for (int i = 0; i < N; i++) { if (parents[i] == -1) { graph = new Graph(i); break; } } for (int i = 0; i < N; i++) { if (parents[i] != -1) graph->insert(i, parents[i]); } int remove; cin >> remove; if (remove == graph->root->value) { cout << 0 << "\n"; return 0; } graph->remove(remove, parents[remove]); int number = 0; graph->find_leaf(graph->root, &number); cout << number << "\n"; return 0; }

제출 #58876

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: