AOJ 2534 Dictionary

問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534)

まず、与えられた文字列の組(string_i, string_j)(i < j)が辞書式順序を満たすようにアルファベットの間に順序を入れていく。アルファベットx, yに順序が入っていることは有向グラフに(x, y)の辺を張ることで表現する。文字列の長さが違うときは'@'(='a' - 1)で埋めておいた。

このグラフの構築段階で(i,j)に辺があるのに(j,i)にも辺が張られているば矛盾しているのでfalseを返す。また、'@'は最小であるはずなのでそれが満たされていない時もfalseを返す。

'@'を始点として辺の張られているアルファベットに深さ優先探索で移動していくとき、もしも矛盾がなければ高々深さは26にしかならないから、それ以上の深さを探索しようとしていたらfalseを返す。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)

bool dfs(int d[][27], int k, int cnt) {
  if(cnt > 30) return false;
  bool flag = true;
  REP(j,27) if(d[k][j] == 1) flag = false;
  if(flag) return true;

  bool res = true;
  REP(j,27){
    if(d[k][j] == 1){
      res = res && dfs(d, j, cnt + 1);
    }
  }
  return res;
}

bool solve(vector<string> &s) {
  int n = s.size();
  int d[27][27] = {0};
  REP(i,n)for(int j = i + 1; j < n; ++j) {
    int pos = 0;
    while(pos < s[i].length() && s[i][pos] == s[j][pos]) pos++;
    if(pos == s[i].length()) continue;
    if(d[s[j][pos]-'a'+1][s[i][pos]-'a'+1] == 1) return false;
    d[s[i][pos]-'a'+1][s[j][pos]-'a'+1] = 1;
  }
  REP(i,27) if(d[i][0] == 1) return false;
  
  return dfs(d, 0, 0);
}

int main(){
  int n;
  while(cin >> n && n) {
    vector<string> s(n);
    REP(i,n) cin >> s[i];
    int lmx = 0;
    REP(i,n) lmx = max(lmx, (int)s[i].length());
    REP(i,n)REP(j,lmx-s[i].length()) s[i] += 'a' - 1;
    if(solve(s)) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}