1514.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1514 on 2006-07-23 at 15:20:27 */ 
#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;

const int MAX = 64;

class Node {
public:
	list<int> adj;
	bool visit;
	void make();
};
void Node::make() {
	adj.clear();
	visit = false;
}

Node node[MAX];

void print(int);

int main()
{
	int d[MAX], seq[MAX];
	int i, p;
	char ch;

	while((ch = getchar()) != EOF) {
		ungetc(ch, stdin);
		int sn = 0, nn = 0, b = 1;
		memset(d, 0, sizeof(d));
		for(sn = 0; true; sn++) {
			ch = getchar();
			if(ch == '\n') break;
			else ungetc(ch, stdin), scanf("%d", &seq[sn]);
			nn = max(nn, seq[sn]); d[seq[sn]]++;
			while((ch = getchar()) == ' ');
			ungetc(ch, stdin);
		}
		for(i = 0; i <= nn; i++) node[i].make();
		for(i = 0; i < sn; i++) {
			for(p = 1; d[p] != 0; p++) ;
			if(i == 0) b = p;
			node[p].adj.push_back(seq[i]); node[seq[i]].adj.push_back(p);
			d[p]--; d[seq[i]]--;
		}
		print(b);
		putchar('\n');
	}
	
	return 0;
}

void print(int o)
{
	printf("(%d", o);
	node[o].visit = true;
	list<int>::iterator it;
	for(it = node[o].adj.begin(); it != node[o].adj.end(); it++) {
		if(!node[*it].visit) {
			putchar(' ');
			print(*it);
		}
	}
	putchar(')');
}