4043189_ac_0ms_204k.cpp

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

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

char map[50][21];
int top[26][26];
int id[256], cnt, d[26];
char alpha[26];

bool cmp(int a, int b)
{
	return alpha[b] < alpha[a];
}

int main()
{
	int n, i, j, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%s", map[i]);
	}
	cnt = 0;
	memset(id, -1, sizeof(id));
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < 20; j++)
		{
			if (map[i][j] != '.' && id[map[i][j]] == -1)
			{
				id[map[i][j]] = cnt;
				alpha[cnt++] = map[i][j];
			}
		}
	}
	memset(top, 0, sizeof(top));
	memset(d, 0, sizeof(d));
	for (i = 0; i < 20; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (map[j][i] == '.')
				continue;
			for (k = j + 1; k < n; k++)
			{
				if (map[k][i] == '.' || map[k][i] == map[j][i])
					continue;
				if (top[id[map[k][i]]][id[map[j][i]]] == 0)
				{
					top[id[map[k][i]]][id[map[j][i]]] = 1;
					d[id[map[j][i]]]++;
				}
			}
		}
	}
	int heap[30];
	int r = 0;
	for (i = 0; i < cnt; i++)
	{
		if (d[i] == 0)
		{
			heap[r++] = i;
			push_heap(heap, heap + r, cmp);
		}
	}
	while (r)
	{
		int v = heap[0];
		putchar(alpha[v]);
		pop_heap(heap, heap + r--, cmp);
		for (i = 0; i < cnt; i++)
		{
			if (top[v][i] == 1)
			{
				d[i]--;
				if (d[i] == 0)
				{
					heap[r++] = i;
					push_heap(heap, heap + r, cmp);
				}
			}
		}
	}
	puts("");
	return 0;
}