AOJ2534 Dictionary

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

アルファベットに対応させることのできる言語が発見されている。
単語が改行区切りで順に書かれている。辞書順が定義されている可能性のある言語かどうか判定せよ。

解説
単語列を同じ長さに変換しておく。空の部分は適当な記号$で埋めておく。
任意の2つの単語について左からループで見ていく。

• 初めて異なる単語になったときに、上方の単語から下方の単語に有向グラフを張ることが出来る。
• 上方が$で、下方に文字がある場合は、ループを脱出する。
• 上方に文字があり、下方が$の場合は、その時点で不適となる。
• 上方と下方のどちらも$の場合は、ループを脱出する
• 同じ文字の場合は次の列の文字に移る

このようにグラフを張ると、辞書順の関係に矛盾がないのならアルファベット同士で連結成分ごとにDAGを形成しているはずである。

よって、グラフの各連結成分がDAGかどうか判定すれば良い。アルファベットが26文字までと少ないので、全てのアルファベットから別々にvisitedを初期化して探索した時にループに突入しないか調べれば良い。

const char premark = 'a' - 1;
 
bool dfs(map<char, vector<char>>& G, vector<bool>& vis, char c) {
  for(auto& next: G[c]) {
    if(vis[next-'a']) return false;
    vis[next-'a'] = 1;
    if(!dfs(G, vis, next)) return false;
    vis[next-'a'] = 0;
  }
  return true;
}
 
void NG() {
  cout << "no" << endl;
}
 
int main() {
 
  for(int N; cin >> N && N;) {
    vector<string> v;
    int L = 1;
    rep(i, N) {
      string s; cin >> s;
      v.push_back(s);
      maximize(L, s.size());
    }
    rep(i, N) {
      v[i].resize(L, premark);
    }
 
    map<char, vector<char>> G;
    vector<bool> vis;
 
    rep(i, N-1) {
      REP(ni, i+1, N) {
        rep(j, L) {
          if(v[i][j] == v[ni][j] && v[i][j] == premark) break;
          if(v[i][j] == premark) break;
          if(v[ni][j] == premark) { NG(); goto ex; }
          if(v[i][j] == v[ni][j]) continue;
          G[v[i][j]].push_back(v[ni][j]);
          break;
        }
      }
    }
 
    REP(c, 'a','z'+1) if(!G[c].empty()) {
      sort(all(G[c]));
      G[c].erase(unique(all(G[c])), G[c].end());
    }
 
    REP(c, 'a','z'+1) {
      vis.clear(); vis.resize(26);
      vis[c-'a'] = 1;
      if(!dfs(G, vis, c)) { NG(); goto ex; }
    }
 
    cout << "yes" << endl;
    ex:;
  }
   
  return 0;
}