Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 2350 | Accepted: 906 |
Description
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
Output
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
AC:直接暴力枚举所有情况,每次都从从节点个数最小的为1的开始;
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
char ss[];
int a[][],num[];
int ans[];
int main()
{
int len;
while(gets(ss))
{
memset(a,,sizeof(a));
memset(ans,,sizeof(ans));
memset(num,,sizeof(num));
len = strlen(ss);
int aa = ,i=,lev=,t=,mmax =,kk=;
for(i = ; i < len; i++)
{
if(ss[i] == '(')
lev++;
else if(ss[i] == ')')
lev--;
if(ss[i] >= '' && ss[i] <= '')
{
t = t * + ss[i] - ;
if(t > mmax)
mmax = t;
if(!(ss[i + ] >= '' && ss[i + ] <= ''))
{
num[lev] = t;
a[num[lev - ]][num[lev]] = ;
a[num[lev]][num[lev - ]] = ;
}
}
else
{
t = ;
}
}
int sum,j,k,m;
for( i=;i<=mmax;i++)
{
for( j=;j<=mmax;j++)
{ sum = ;
for(k=;k<=mmax;k++)//统计和他相连的数的个数
{
sum = sum+a[j][k];
}
if(sum == )
{
for(m = ;m<=mmax; m++)
if(a[j][m] == )
{
ans[kk++] = m;
a[j][m] = ;
a[m][j] = ;
j = ;
break;
}
}
}
}
for(int i=; i<kk; i++)
if(i == )printf("%d",ans[i]);
else printf(" %d",ans[i]);
printf("\n");
}
return ;
}