Timus 1069. The Prufer code

时间：2010-10-09 来源：晓天

* File: Timus 1069. The Prufer code
* Author: xiaotian @ hnu
* Created on 2010年10月9日, 上午9:35
* 题解：思维题目。给定一棵树的编码方式，让还原这棵树。
* 编码方式：每次取编号最小的叶节点和与其相连的边删掉，写下这个叶节点的父亲节点。重复以上操作，直到只有一个节点的时候，这个节点编号必然是 n 。
* 还原方式：可以发现，不在后面出现的节点必然是目前这棵树的叶节点，所以用优先队列维护一个后面不再出现的节点的集合，然后用队首元素与当前节点连边即可。

代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define N 8000
#define inf 0x7ffffff
vector<int>g[N];
int n, id[N],last[N];

struct node {
    int k;
    node(int a = 0) : k(a) {}
    bool operator<(const node & r) const { return r.k<k; }
};
priority_queue<node>q;

int main() {
    int k;
    n = 0;
    memset(last, -1, sizeof (last));
    while (scanf("%d", &k) != EOF) { id[n] = k; last[k] = n++; }
    n++; while (!q.empty()) q.pop();
    for (int i = 1; i <= n; i++) {
        if (last[i] == -1) q.push(node(i));
        g[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
        k = q.top().k; q.pop();
        g[k].push_back(id[i]);
        g[id[i]].push_back(k);
        if (i == last[id[i]]) q.push(node(id[i]));
    }
    for (int i = 1; i <= n; i++) {
        printf("%d:", i);
        sort(g[i].begin(), g[i].end());
        for (int j = 0; j < g[i].size(); j++)
            printf(" %d", g[i][j]);
        puts("");
    }
    return 0;
}