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 
#include 
#include 
#include 
#include 
#define MAX 110
using namespace std;

priority_queue,greater > 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;
}

#include 
#include 
#include 
#include 
#include 
#include 
#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,greater > 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;
}