Perfect Keyboard

codeforces.com

問題

アルファベット26文字が1列に並ぶキーボードを考える。いま、パスワードがN個与えられる。キーボードの配列をうまく組み替えることで、隣接したキー間の移動のみでパスワードを入力することができるか?

入出力例

入力

はじめにパスワードの数Nが与えられる。 以下N行にパスワードが与えられる

5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

たとえば1つ目のパスワードはabが隣接していれば入力することができる。しかし、3つ目はdとaを隣接して配置できないため、入力できない。

出力

YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

解説

この問題は「閉路を含まず、枝分かれのない木が1つだけ存在するグラフか?」と言い換えることができる。左右にしか移動できないという条件からこれが言える。

まず、枝分かれがないことを確認する。もし、次数が3以上の頂点があればその時点でNO。

次に、端が存在することを確認(次数が1の頂点が端)。もし端がなければ閉路となっているのでNO。

連結成分が2つ以上あるケースというのはそもそも存在しないので、以上で存在するかの判定は終了する。

あとはこの点からはじめて順にたどれば単純パスが完成する。その単純パスを先頭に並べて、残ったアルファベットを列挙すればAC。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

int main() {
  int in(N);

  rep(i, N) {
    string in(s);
    if (s.size() == 1) {
      // 1つだけならa-zで対応できる
      cout << "YES\nabcdefghijklmnopqrstuvwxyz\n";
      continue;
    }
    vector<int> edge(26, 0);
    rep(j, s.size()-1) {
      edge[s[j]-'a'] |= (1 << (int)(s[j+1]-'a'));
      edge[s[j+1]-'a'] |= (1 << (int)(s[j]-'a'));
    }

    // 単純パスを見つける
    int start = -1;
    bool ok = true;
    rep(j, s.size()) {
      if (__builtin_popcount(edge[s[j]-'a']) == 1)
        start = s[j]-'a';
      if (__builtin_popcount(edge[s[j]-'a']) > 2)
        ok = false;
    }

    // 閉路しかない
    if (start == -1)
      ok = false;
    if (!ok) {
      cout << "NO\n";
      continue;
    }

    vector<bool> visited(26, false);
    queue<int> q; q.push(start);
    vector<char> ans;
    while (!q.empty()) {
      int p = q.front(); q.pop();
      if (visited[p])
        continue;
      visited[p] = true;
      ans.push_back((char)(p+'a'));
      rep(j, 26)
        if (edge[p] & (1 << j))
          q.push(j);
    }

    cout << "YES\n";
    for (const auto& e : ans)
      cout << e;
    rep(j, 26) {
      if (visited[j])
        continue;
      cout << (char)(j+'a');
    }
    cout << endl;
  }

  return 0;
}