第二题:

2567:Code the Tree

题目链接：

P2567——Code the Tree——柒行（www.oj7.cn）

题目来源：

Ulm Local 2001

题目描述

总时间限制:

1000ms

内存限制:

65536kB

描述

A tree (i.e. a connected graph without cycles) with vertices numbered by the integers 1, 2, ..., n is given. The "Prufer" code of such a tree is built as follows: the leaf (a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down. In the obtained graph, this procedure is repeated, until there is only one vertex left (which, by the way, always has number n). The written down sequence of n-1 numbers is called the Prufer code of the tree. Your task is, given a tree, to compute its Prufer code. The tree is denoted by a word of the language specified by the following grammar:

T ::= "(" N S ")"
S ::= " " T S
    | empty
N ::= number

That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many (maybe none) subtrees separated by a single space character. As an example, take a look at the tree in the figure below which is denoted in the first line of the sample input. To generate further sample input, you may use your solution to Problem 2568. Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an "unrooted tree".

输入

The input contains several test cases. Each test case specifies a tree as described above on one line of the input file. Input is terminated by EOF. You may assume that 1<=n<=50.

输出

For each test case generate a single line containing the Prufer code of the specified tree. Separate numbers by a single space. Do not print any spaces at the end of the line.

输入数据

(2 (6 (7)) (3) (5 (1) (4)) (8))
(1 (2 (3)))
(6 (1 (4)) (2 (3) (5)))

输出数据

5 2 5 2 6 2 8
2 3
2 1 6 2 6

中文题面：

描述

给定一棵用整数$1, 2, ..., n$编号的树（即无环的连通图）。这棵树的"Prufer"编码构建方式如下： 选择编号最小的叶子节点（只连接一条边的顶点），将该叶子节点及其连接的边从图中移除，并记录下与该叶子节点相邻的顶点的编号。在剩下的图中重复这个过程，直到只剩下一个顶点（根据定义，这个顶点总是编号为$n$的顶点）。 记录下的$n-1$个编号序列即为该树的Prufer编码。 你的任务是，给定一棵树，计算它的Prufer编码。树的表示方式遵循以下语法规则：

T ::= "(" N S ")"
S ::= " " T S
    | empty
N ::= number

也就是说，树被括号包围，括号内是一个表示根顶点编号的数字，后面跟着任意数量（可能为零）的子树，子树之间用单个空格分隔。例如，样例输入中的第一行表示的图可以参见下图。你可以使用问题2568的解决方案来生成更多的样例输入。 需要注意的是，根据上面的定义，树的根顶点也可能是一个叶子节点。 我们指定一个顶点作为根只是为了表示方便。通常情况下，我们处理的是"无根树"。 输入： 输入包含多个测试用例。每个测试用例在一行中按照上述语法规则描述了一棵树。输入以文件结束符（$EOF$）结束。假设 $1<=n<=50$。 输出： 对于每个测试用例，输出一行包含该树对应的Prufer编码。编码中的数字用单个空格分隔。行尾不要输出任何空格。

输入数据

(2 (6 (7)) (3) (5 (1) (4)) (8))
(1 (2 (3)))
(6 (1 (4)) (2 (3) (5)))

输出数据

5 2 5 2 6 2 8
2 3
2 1 6 2 6

算法标签

树结构解析 优先队列（最小堆） Prüfer编码

解题思路：

将括号嵌套的字符串转换为树的邻接表表示，记录每个节点的邻居关系和度数。统计所有节点的度数，将初始叶子节点（度数为$1$的节点）加入最小堆。循环从堆中取出最小叶子节点，记录其唯一邻居，更新邻居的度数。若邻居变为新叶子，则加入堆中。当剩余节点数为$1$时停止，此时Prüfer码长度为 $n−1$ 。

实现步骤：

解析输入字符串：

使用栈处理括号嵌套，递归解析每个子树。遇到(时读取当前节点编号，建立与父节点的边。 更新邻接表和度数。

初始化优先队列：

遍历邻接表，将度数为$1$的节点加入最小堆。

生成Prüfer码：

循环取出堆顶元素（最小叶子节点），找到其唯一未被删除的邻居。将该邻居加入Prüfer序列，减少其度数。若邻居变为叶子节点，则入堆。重复直到只剩一个节点。

输出结果：

按格式输出Prüfer序列，确保末尾无空格。

C++实现：

#include <iostream>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cctype>
#include <algorithm>  // 添加algorithm头文件
using namespace std;

// 解析输入的树结构字符串，构建邻接表
void parse_tree(const string& s, map<int, vector<int> >& adj) {
    stack<int> st; // 用于追踪当前节点的父节点
    int i = 0, n = s.size();
    while (i < n) {
        if (s[i] == '(') { // 遇到左括号，处理新节点
            i++;
            while (i < n && isspace(s[i])) i++; // 跳过空格
            int num = 0;
            // 读取数字（节点编号）
            while (i < n && isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            // 如果栈非空，说明有父节点，建立双向连接
            if (!st.empty()) {
                int parent = st.top();
                adj[parent].push_back(num);
                adj[num].push_back(parent);
            }
            st.push(num); // 当前节点入栈
        } else if (s[i] == ')') { // 遇到右括号，回退到父节点
            if (!st.empty()) st.pop();
            i++;
        } else { // 其他字符直接跳过
            i++;
        }
    }
}

// 根据邻接表生成Prufer编码
vector<int> generate_prufer(map<int, vector<int> >& adj) {
    map<int, int> degree; // 记录每个节点的度数
    // 小顶堆，用于快速获取最小叶子节点
    priority_queue<int, vector<int>, greater<int> > min_heap;

    // 初始化度数和堆
    for (map<int, vector<int> >::iterator it = adj.begin(); it != adj.end(); ++it) {
        int u = it->first;
        vector<int>& neighbors = it->second;
        degree[u] = neighbors.size(); // 度数等于邻接节点数
        if (degree[u] == 1) { // 初始叶子节点入堆
            min_heap.push(u);
        }
    }

    vector<int> prufer; // 保存生成的Prufer码
    int remaining = adj.size(); // 剩余节点数

    while (remaining > 1) { // 直到只剩一个节点
        // 跳过已删除的非叶子节点
        while (!min_heap.empty() && degree[min_heap.top()] != 1) {
            min_heap.pop();
        }
        if (min_heap.empty()) break;

        int u = min_heap.top(); // 取出最小叶子节点
        min_heap.pop();

        int v = -1;
        vector<int>& neighbors = adj[u];
        // 寻找与u相连的第一个有效节点（未被删除的）
        for (size_t i = 0; i < neighbors.size(); ++i) {
            int neighbor = neighbors[i];
            if (degree[neighbor] > 0) { // 确保节点仍在树中
                v = neighbor;
                break;
            }
        }
        prufer.push_back(v); // 记录相邻节点
        degree[u] = 0; // 标记u已被删除
        degree[v]--; // 减少v的度数
        if (degree[v] == 1) { // 如果v成为叶子节点，加入堆
            min_heap.push(v);
        }
        remaining--; // 减少剩余节点计数
    }
    return prufer;
}

int main() {
    string line;
    while (getline(cin, line)) { // 处理多组输入
        map<int, vector<int> > adj; // 邻接表
        parse_tree(line, adj); // 解析输入为邻接表
        vector<int> code = generate_prufer(adj); // 生成Prufer码
        // 格式化输出
        for (size_t i = 0; i < code.size(); ++i) {
            if (i > 0) cout << " ";
            cout << code[i];
        }
        cout << endl;
    }
    return 0;
}