* File: Timus 1069. The Prufer code
* Author: xiaotian @ hnu
* Created on 2010年10月9日, 上午9:35
* 题解：思维题目。给定一棵树的编码方式，让还原这棵树。
* 编码方式：每次取编号最小的叶节点和与其相连的边删掉，写下这个叶节点的父亲节点。重复以上操作，直到只有一个节点的时候，这个节点编号必然是 n 。
* 还原方式：可以发现，不在后面出现的节点必然是目前这棵树的叶节点，所以用优先队列维护一个后面不再出现的节点的集合，然后用队首元素与当前节点连边即可
。
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<queue>
5 using namespace std;
6 #define N 8000
7 #define inf 0x7ffffff
8 vector<int>g[N];
9 int n, id[N],last[N];
10
11 struct node {
12 int k;
13 node(int a = 0) : k(a) {}
14 bool operator<(const node & r) const { return r.k<k; }
15 };
16 priority_queue<node>q;
17
18 int main() {
19 int k;
20 n = 0;
21 memset(last, -1, sizeof (last));
22 while (scanf("%d", &k) != EOF) { id[n] = k; last[k] = n++; }
23 n++; while (!q.empty()) q.pop();
24 for (int i = 1; i <= n; i++) {
25 if (last[i] == -1) q.push(node(i));
26 g[i].clear();
27 }
28 for (int i = 0; i < n - 1; i++) {
29 k = q.top().k; q.pop();
30 g[k].push_back(id[i]);
31 g[id[i]].push_back(k);
32 if (i == last[id[i]]) q.push(node(id[i]));
33 }
34 for (int i = 1; i <= n; i++) {
35 printf("%d:", i);
36 sort(g[i].begin(), g[i].end());
37 for (int j = 0; j < g[i].size(); j++)
38 printf(" %d", g[i][j]);
39 puts("");
40 }
41 return 0;
42 }