hoj12614 Dictionary ——拓扑排序找环&&比赛残留题

April 29, 2013
Graph

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12614&courseid=247 题目大意：　　有一种字典。把字典中的符号映射到英文字母。输入一个n，然后是n行映射后的单词，判断这n个单词是不是符合字典序，所谓字典序就是前面的单词可以是后面的单词的前缀，并且这n个单词符合字符串排序后的顺序，这是针对原来的字母的，而不是映射之后的字母。题目思路：　　需要考虑映射之后的字母的相对顺序，来考虑是不是在原来的字母表中是不是符合字典序。　　这道题目开始没看懂，最关键的第一段描述没有注意到，结果样例都看不懂。纠结了好久。但是涉及到前缀，觉得应该是字典树。　　后来终于注意到第一段了，终于理解题目意思了。悲剧的是，还是纠结在字典树上面，老是在这方面想。没有思路。知道考虑相对顺序，但是不知道怎么映射……过程中llh其实提到了一下两个字母的相对顺序可以用边表示，可是，我没有继续往下想！后来听人家说，可以建图，然后找环。唉，原来就是llh那样想的。　　回来之后，认真想了一下。方法是：预处理的过程中判断是不是出现这种情况：后面的单词是前面的单词的前缀，这是不符合条件的。同时在预处理的过程中建图，用临界表，如果一个字母A在另一个字母B的后面，就把B插入到A的出边表里面。然后就是在这个图里面找环，如果出现环了，就是不符合条件的。找环的方法就是刚刚做过的拓扑排序的方法。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
int n; char a[509][17];
struct ArcNode {
  int to; struct ArcNode *next;
};
ArcNode *List[50];
int Count[50];
bool topsort()
{
  int i = 0, j, k, top = -1;
  ArcNode *temp; bool flag = false;
  for (i = 0; i < 26; ++i) {
    if (Count[i] == 0) { Count[i] = top; top = i; }
  }
  for (i = 0; i < 26; ++i) {
    if (top == -1) { flag = true; break; }
    j = top; top = Count[top]; temp = List[j];
    while (temp) {
      k = temp->to; Count[k]--;
      if (Count[k] == 0) { Count[k] = top; top = k; }
      temp = temp->next;
    }
  }
  if (flag) return false;
  else return true;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("hnu247.in", "r", stdin);
#endif
  while (~scanf("%d", &n)) {
    if (!n) break;
    int i, j, u, v; bool flag = true; ArcNode *temp;
    for (i = 0; i < n; ++i) {
      scanf("%s", a[i]);
    }
    memset(List, 0, sizeof(List));
    for (i = 0; i < 27; ++i) Count[i] = 0;
    for (i = 1; i < n; ++i) {
      for (j = 0; j < strlen(a[i-1]); ++j) {
        if (j >= strlen(a[i])) { flag = false; break; }
        if (a[i-1][j] != a[i][j]) {
          u = a[i-1][j] - 'a'; v = a[i][j] - 'a';
          Count[v]++; temp = new ArcNode;
          temp->to = v; temp->next = NULL;
          temp->next = List[u]; List[u] = temp;
          break;
        }
      }
      if (!flag) break;
    }
    if (!flag) { printf("no\n"); continue; }
    if (topsort()) { printf("yes\n"); }
    else printf("no\n");
  }

  return 0;
}

　　做题的时候还是有个误区：第一感觉这道题目应该用到什么数据结构或算法，就硬往里面套，结果，很限制思路。其实应该是，先认真分析这道题目，是解决什么问题的，应该怎么解决，然后在思考可能什么样的数据结构或者算法能起作用。而不是硬生生的套数据结构，一条路走到黑…… 　　很多人过这道题目，分析完之后，其实这应该也是很基础的一道题目。也许是自己做的太少了，当时想法都没有……

Read more