Description
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”.
Input
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.
Output
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.
Sample Input
(2 (6 (7)) (3) (5 (1) (4)) (8))
(1 (2 (3)))
(6 (1 (4)) (2 (3) (5)))
Sample Output
5 2 5 2 6 2 8
2 3
2 1 6 2 6
题目大意
树的顶点,用整数1,2,3,n……编号.Prufer码是按如下构造:找到编号最小的叶结点(只有一条边与之相连).将该叶结点,及其相连的边从图中删除,记下与之相连的节点编号,重复上述步骤,直至剩下最后一个节点.
算法分析
分析
就拿上图举例,首先找到编号最小的叶结点,编号是1;将该叶结点及所在边去掉,并记下与之相连的节点编号:5.
接着去找编号最小的叶结点,编号是3;将该叶结点及所在边去掉,并记下与之相连的节点编号:2.
不断重复知道输出完(输出的结果个数应该比原输入的个数小1).数据结构
需要用到STL里的Vector()和Set()(详见代码注释中)实现Prufer码
当某节点只有一个相邻节点时,它就是叶子节点.将所有这些叶子节点放到一个优先队列中,选出节点编号最小的那个节点,输出其相邻的节点编号,就是该节点的Prufer码.对于上表而言,初始状态的叶子节点是
1,3,4,7,8
将这些节点放到优先队列中排序,就获得了编号最小的叶子节点1,输出相邻的节点编号5,同时将5相邻的节点1删除,如果5只有一个节点,则进入优先队列.
程序代码
#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
void parse( vector<set<int> >&adj,unsigned int p=0)
{
unsigned int x;
cin>>ws>>x; //x表示当前读的数
if(p) //p表示前一个数
{
adj[x].insert(p); //set容器没有重复的数据,若多次插入相同数据,容器内只有一种
adj[p].insert(x); //此处节点相邻是对称的
}
//递归读取数据
while(true) //为了不断读取同样级别
{
char ch; //读符号
cin>>ws>>ch;
if(ch==')')
break;
parse(adj,x);
}
return ;
}
int main()
{
char ch;
while(cin>>ws>>ch) //ws是ios的控制符,读空格的意思(不止读一个,有才读,没有不读)
{
int n=0;//节点数
vector<set<int>/*有空格区别于">>"*/ >adj (1024,set<int>());//vector里的每一个数据都set<int>初始化
parse(adj);
priority_queue<int,vector<int>,greater<int> >leafs;//优先队列
for(unsigned int i=0;i<adj.size();i++)
{
if(adj[i].size())
{
n++;
if(adj[i].size()==1)//如果只有一个成员就放入队列
leafs.push(i);
}
}
//处理优先队列
for(unsigned int i=1;i<n;i++)//n次输出,永远比输入少1
{
unsigned int x,p;
x=leafs.top();
leafs.pop();
p=*(adj[x].begin());//数组adj元素是集合,获取集合的元素用指针
if(i>1)//第一个数前没空格,后面的数之间有空格
cout<<" ";
cout<<p;
adj[p].erase(x);//删除对应节点p中的x
//如果p节点也成为叶子节点,则进入优先队列
if(adj[p].size()==1)
leafs.push(p);
}
cout<<endl;
}
return 0;
}