POJ 2567 - Code the Tree

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

概要

ノードに \(1 \ldots n\) の数値のラベルを持つサイズ \(n\) の根付き木が与えられるので、これを Prufer code に変換したものを答える。

Prufer code は次のようにして得られる。 まず葉ノード(ここでは1つのエッジしか持たないノードのことを葉ノードと呼ぶ)のうち最も小さいラベルをもつノードを選ぶ。 そしてそのノードが唯一接続している相手のノードのラベルが Prufer code として書き足され、木からそのノードとそのノードが持つ唯一のエッジを削除する。 この手順をノードが1つになるまで \(n-1\) 回繰り返す。

制約

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

解法

\(n\) が小さいので、接続関係を隣接行列で持って愚直にシミュレートする。

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 typedef string::const_iterator Iterator;
 6 
 7 int number(Iterator& it, const Iterator& last)
 8 {
 9   int n = 0;
10   while (it != last && '0' <= *it && *it <= '9') {
11     n = 10*n + *it-'0';
12     ++it;
13   }
14   return n-1;
15 }
16 
17 int parse(bool g[50][50], Iterator& it, const Iterator& last)
18 {
19   if (*it != '(') {
20     throw "e";
21   }
22   ++it;
23   int u = number(it, last);
24   while (*it == '(') {
25     int v = parse(g, it, last);
26     g[u][v] = g[v][u] = true;
27   }
28   if (*it != ')') {
29     throw "f";
30   }
31   ++it;
32   return u;
33 }
34 
35 int main()
36 {
37   for (string line; getline(cin, line);) {
38     bool g[50][50];
39     for (int i = 0; i < 50; i++) {
40       fill_n(g[i], 50, 0);
41     }
42     line.erase(remove(line.begin(), line.end(), ' '), line.end());
43     Iterator it = line.begin(), last = line.end();
44     parse(g, it, last);
45 
46     int deg[50];
47     fill_n(deg, 50, 0);
48     for (int i = 0; i < 50; i++) {
49       for (int j = 0; j < 50; j++) {
50         if (g[i][j]) {
51           ++deg[j];
52         }
53       }
54     }
55     for (int t = 0; t < 50; t++) {
56       for (int i = 0; i < 50; i++) {
57         if (deg[i] == 1) {
58           --deg[i];
59           for (int j = 0; j < 50; j++) {
60             if (g[i][j]) {
61               g[i][j] = g[j][i] = false;
62               --deg[j];
63               if (t != 0) {
64                 cout << " ";
65               }
66               cout << j+1;
67               goto NEXT;
68             }
69           }
70         }
71       }
72 NEXT:
73       ;
74     }
75     cout << endl;
76   }
77   return 0;
78 }