首页 > 代码库 > POJ 2567 Code the Tree & POJ 2568 Decode the Tree Prufer序列

POJ 2567 Code the Tree & POJ 2568 Decode the Tree Prufer序列

题目大意:2567是给出一棵树,让你求出它的Prufer序列。2568时给出一个Prufer序列,求出这个树。


思路:首先要知道Prufer序列。对于任意一个无根树,每次去掉一个编号最小的叶子节点,并保存这个节点所连接的节点所得到的序列就是这棵树的Prufer序列。这个序列有十分优雅的性质,它能与无根树一一对应。因此,两个标号一样的无根树得到的Prufer序列也一定是一样的。此外,设一个节点的度数是d[i],那么他会在Prufer序列中出现d[i] - 1次。

2567:记录每一个节点的度,按照Prufer序列的定义,最后输出队列中剩余的元素。

2568:由Prufer序列能够求出每个点的度,把度数为1的点加入到队列中去,每次找一个队列中编号最小的,与当前Prufer序列中的数字连一条边,然后减少相应的度数。


CODE(2567):


#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 110
using namespace std;

priority_queue<int,vector<int>,greater<int> > q;

int points;
int degree[MAX];
int head[MAX],total;
int next[MAX << 1],aim[MAX << 1];

int stack[MAX],top;
bool v[MAX];

inline void Initialize()
{
	points = total = top = 0;
	memset(degree,0,sizeof(degree));
	memset(v,false,sizeof(v));
	memset(head,0,sizeof(head));
}

inline void Add(int x,int y)
{
	next[++total] = head[x];
	aim[total] = y;
	head[x] = total;
}

inline char GetChar()
{
	char c;
	do c = getchar(); while(c == ' ' || c == '\n' || c == '\r');
	return c;
}

inline void TopSort()
{
	for(int i = 1; i <= points; ++i)
		if(degree[i] == 1)
			q.push(i),v[i] = true;
	for(int i = 1; i <= points - 2; ++i) {
		int x = q.top(); q.pop();
		for(int j = head[x]; j; j = next[j]) {
			if(v[aim[j]])	continue;
			--degree[aim[j]];
			printf("%d ",aim[j]);
			if(degree[aim[j]] == 1) {
				v[aim[j]] = true;
				q.push(aim[j]);
			}
		}
	}
	q.pop();
	printf("%d\n",q.top());
	q.pop();
}

int main()
{
	char c;
	while(GetChar() != EOF) {
		Initialize();
		scanf("%d",&stack[++top]);
		points = stack[top];
		while(top) {
	 		c = GetChar();
			if(c == '(') {
				int temp;
				scanf("%d",&temp);
				points = max(points,temp);
				Add(stack[top],temp);
				Add(temp,stack[top]);
				++degree[stack[top]];
				++degree[temp];
				stack[++top] = temp;
			}
			else	top--;
		}
		if(points == 1) {
			puts("");
			continue;
		}
		TopSort();
	}
	return 0;
}



CODE(2568):


#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 1010
using namespace std;

char s[MAX];
int src[MAX],cnt;
int degree[MAX];
int head[MAX],total;
int next[MAX],aim[MAX];
int points;

inline void Initialize()
{
	total = cnt = points = 0;
	memset(degree,0,sizeof(degree));
	memset(head,0,sizeof(head));
}

inline void Add(int x,int y)
{
	next[++total] = head[x];
	aim[total] = y;
	head[x] = total;
}

inline void Decode()
{	
	static priority_queue<int,vector<int>,greater<int> > q;
	while(!q.empty())	q.pop();
	for(int i = 1; i <= points; ++i)
		if(!degree[i])	q.push(i);
	for(int i = 1; i <= cnt; ++i) {
		int x = src[i];
		int y = q.top(); q.pop();
		Add(x,y); Add(y,x);
		if(!--degree[x])	q.push(x);
	}
	//int x = q.top(); q.pop();
	//int y = q.top(); q.pop();
	//Add(x,y),Add(y,x);
}

inline void OutPut(int x,int last)
{
	if(x != 1)	putchar(' ');
	putchar('(');
	printf("%d",x);
	for(int i = head[x]; i; i = next[i]) {
		if(aim[i] == last)	continue;
		OutPut(aim[i],x);
	}
	putchar(')');
}

int main()
{
	while(gets(s) != NULL) {
		Initialize();
		char *p = s;	
		while(*p != '\0') {
			sscanf(p,"%d",&src[++cnt]);
			points = max(points,src[cnt]);
			++p,++p;
			if(src[cnt] > 9)	++p;
		}
		memset(s,'\0',sizeof(s));
		for(int i = 1; i <= cnt; ++i)
			++degree[src[i]];
		Decode();
		OutPut(1,0);
		puts("");
	}
	return 0;
}



POJ 2567 Code the Tree & POJ 2568 Decode the Tree Prufer序列