[백준][C++]1068번 트리

 

문제

https://www.acmicpc.net/problem/1068

1068번: 트리

 

 

풀이

트리(Tree) 자료구조

트리(Tree) 자료구조

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

void deleteNode(int n);
static int N;
static vector<int> parent;
static vector<vector<int>> children;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> N;

  parent.resize(N + 1);
  children.resize(N + 1);
  for(int i = 0; i < N; i++)
  {
    int num;
    cin >> num;

    parent[i] = num;
    if(num != -1)
    {
      children[num].push_back(i);
    }
  }

  int del;
  cin >> del;

  deleteNode(del);

  int leaf = 0;
  for(int i = 0; i < N; i++)
  {
    if(parent[i] != -2 && children[i].size() == 0)
    {
      leaf++;
    }
  }

  cout << leaf;

  return 0;
}

void deleteNode(int n)
{
  parent[n] = -2;
  for(int i = 0; i < N; i++)
  {
    for(int j = 0; j < children[i].size(); j++)
    {
      if(children[i][j] == n)
      {
        children[i].pop_back();
      }
    }
  }

  for(int child : children[n])
  {
    deleteNode(child);
  }
}