８．２ 根付き木の表現（手動編）

解説を見ないで書いた版です。構造体 Node の子の表現を vector にしました。しかし解説では「左右の子のみでも解ける方法」となっており、vector は仰々しかったかなと。。深さの算出は再帰です。子の数が０になるまで回します。

節の入力時の番号が、０からのインクリメンタル値と思い込んでいて、なかなか答えが合わずに苦労しました（実際はランダムで入力される）。

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>

using namespace std;

struct Node {
  int id;
  int parent;
  int depth;
  vector<int> child;
  
  Node() : id(), parent(-1), depth(0), child(0, 0) {}
};

static vector<Node> TREE(100000);

static void inputNode(Node& node, int id, int k) {
  node.id = id;

  int c;
  for (int i = 0; i < k; i++) {
    cin >> c;
    node.child.push_back(c);
  }
}

static const string ROOT = "root";
static const string INTERNAL_NODE = "internal node";
static const string LEAF = "leaf";

static const string& getNodeType(const Node& node) {
  if (node.parent == -1) {
    return ROOT;
  } else if (node.child.size() != 0) {
    return INTERNAL_NODE;
  } else {
    return LEAF;
  }
}

static void setDepth(vector<Node>& tree, Node& node) {
  for (int i : node.child) {
    tree[i].depth = node.depth + 1;
    setDepth(tree, tree[i]);
  }
}

static void setupTree(vector<Node>& tree, int num) {
  for (int i = 0; i < num; i++) {
    const Node& node = tree[i];
    for (int j : node.child) {
      tree[j].parent = node.id;
      tree[j].depth = node.depth + 1;
      setDepth(tree, tree[j]);
    }
  }
}

static void printTree(const vector<Node>& tree, int num) {
  int node, parent = -1, depth = 0;

  for (int i = 0; i < num; i++) {
    const string type = getNodeType(tree[i]);
    printf("node %d: parent = %d, depth = %d, %s, [", i, tree[i].parent, tree[i].depth, type.c_str());
    for (int j  = 0; j < tree[i].child.size(); j++) {
      if (j != 0) {
        printf(", "); 
      }
      printf("%d", tree[i].child[j]);
    }
    printf("]\n");
  }
}

int main() {
  int n;
  cin >> n;

  int id, k;
  for (int i = 0; i < n; i++) {
    cin >> id >> k;
    inputNode(TREE[id], id, k);
  }
  
  setupTree(TREE, n);
  printTree(TREE, n);

  return 0;
}