3535471_ac_16ms_252k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <sstream>
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

typedef vector <int> VI;

const int N = 201;
VI tree[N];
char str[500];
string in;
int node[N];
int n;
int d[N];
int heap[N], r;

void output(int root)
{
	putchar('(');
	printf("%d", root);
	for (int i = 0; i < tree[root].size(); i++)
	{
		putchar(' ');
		output(tree[root][i]);
	}
	putchar(')');
}

int main()
{
	int i, v;

	while (gets(str) != NULL)
	{
		if (strlen(str) == 0)
		{
			puts("(1)");
			continue;
		}
		n = 0;
		memset(d, 0, sizeof(d));
		in = str;
		stringstream ss (in);
		while (ss >> node[n])
		{
			d[node[n]]++;
			n++;
		}
		r = 0;
		for (i = 1; i <= n + 1; i++)
		{
			tree[i].clear();
		}
		for (i = 1; i <= n + 1; i++)
		{
			if (d[i] == 0)
			{
				heap[r++] = i;
				push_heap(heap, heap + r, greater <int> ());
			}
		}
		for (i = 0; i < n; i++)
		{
			v = node[i];
			tree[v].push_back(heap[0]);
			d[v]--;
			pop_heap(heap, heap + r, greater <int> ());
			r--;
			if (d[v] == 0)
			{
				heap[r++] = v;
				push_heap(heap, heap + r, greater <int> ());
			}
		}
		output(n + 1);
		puts("");
	}
	return 0;
}