1513.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1513 on 2005-12-13 at 17:44:29 */ 
#include <cstdio>
#include <list>
using namespace std;

const int MAX = 64;
const int INF = 10000000;

class Node {
public:
	int adjn, id;
	int order;
	list<int> adj;
	void clear();
	void link(Node&);
};
void Node::clear() {
	adj.clear();
	adjn = 0;
}
void Node::link(Node& n) {
	adjn++;
	n.adjn++;
	adj.push_back(n.order);
	n.adj.push_back(order);
}

Node node[MAX];
int n;

void readTree();

int main()
{
	int i, j;
	char ch;
	
	for(i = 0; i < MAX; i++) {
		node[i].order = i;
	}
	while((ch = getchar()) != EOF) {
		n = 0;
		ungetc(ch, stdin);
		readTree();
		for(i = 1; i < n; i++) {
			if(i != 1) {
				putchar(' ');
			}
			int min = INF, mini;
			for(j = 0; j < n; j++) {
				if(node[j].adjn == 1 && min > node[j].id) {
					min = node[j].id;
					mini = j;
				}
			}
			if(min == INF) {
				break;
			} else {
				node[mini].adjn--;
				int o = *(node[mini].adj.begin());
				printf("%d", node[o].id);
				list<int>::iterator it;
				for(it = node[o].adj.begin(); it != node[o].adj.end(); it++) {
					if(*it == mini) {
						node[o].adj.erase(it);
						break;
					}
				}
				node[o].adjn--;
			}
		}
		putchar('\n');
		getchar();
	}
	
	return 0;
}

void readTree()
{
	getchar();
	int cur = n;
	node[n].clear();
	scanf("%d", &node[n++].id);
	while(getchar() == ' ') {
		int p = n;
		readTree();
		node[cur].link(node[p]);
	}
}