POJ 2568 - Decode the Tree

http://poj.org/problem?id=2568

概要

Prufer code が与えられるので、それで表された根付き木を1つ答える (Special Judge)。 Prufer code は POJ 2567 - Code the Tree を参照。

制約

• \(1 \le n \le 50\)

解法

たとえば最初の Sample Input の場合、Prufer code の性質から

• 5は2つの子ノードをもつ
• 2は3つの子ノードをもつ
• 6は1つの子ノードをもつ
• 8は1つの子ノードをもつ
• 1, 3, 4, 7 は子ノードをもたない (葉ノード)

ということがわかる。

Prufer code の順に葉ノードの集合から最も小さいものを子ノードとして追加していく。 子ノードを追加した結果そのノードにこれ以上子ノードを追加できなくなった場合、そのノードを新たに葉ノードの集合に加える。 このとき葉ノードの集合は priority_queue で管理して小さいノードから取り出せるようにしておく。

コーナーケースとして、サイズが1の木の Prufer code は空文字列、つまり空行として入力がくることに注意する (これで何度も Runtime Error を出した…)。

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 void show(const vector<int> *g, int n)
 9 {
10   cout << '(' << n+1;
11   for (vector<int>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
12     cout << ' ';
13     show(g, *it);
14   }
15   cout << ')';
16 }
17 
18 int main()
19 {
20   for (string line; getline(cin, line);) {
21     if (line.empty()) {
22       cout << "(1)" << endl;
23       continue;
24     }
25     istringstream iss(line);
26     vector<int> v;
27     for (int n; iss >> n;) {
28       v.push_back(n-1);
29     }
30     static vector<int> g[50];
31     for (int i = 0; i < 50; i++) {
32       g[i].clear();
33     }
34     int children[50];
35     fill_n(children, 50, 0);
36     for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {
37       ++children[*it];
38     }
39 
40     priority_queue<int> q;
41     for (int i = 0; i < 50; i++) {
42       if (children[i] == 0) {
43         q.push(-i);
44       }
45     }
46     for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {
47       const int n = -q.top();
48       q.pop();
49       g[*it].push_back(n);
50       --children[*it];
51       if (children[*it] == 0) {
52         q.push(-*it);
53       }
54     }
55     show(g, v.back());
56     cout << endl;
57   }
58   return 0;
59 }