2013年1月24日

UVa 200 - Rare Order


#include <stdio.h>

int main() {
  char s[30], prev[30] = {};
  int i, j, con[26] = {}, find[26] = {}, adj[26][26] = {};
  while (gets(s) && s[0] != '#') {
    for (i = 0; s[i]; i++) find[s[i] - 'A'] = 1;
    for (i = 0; s[i] && prev[i] && s[i] == prev[i]; i++);
    if (prev[i] && s[i]) adj[prev[i] - 'A'][s[i] - 'A'] = 1;
    sscanf(s, "%s", prev);
  }
  for (i = 0; i < 26; i++)
    for (j = 0; j < 26; j++)
      if (adj[i][j]) con[j]++;
  while (1) {
    for (i = 0; i < 26 && (!find[i] || con[i]); i++);
    if (i == 26) break;
    con[i] = -1;
    putchar(i + 'A');
    for (j = 0; j < 26; j++)
      if (adj[i][j]) con[j]--;
  }
  puts("");
  return 0;
}

沒有留言:

張貼留言