問題
アルファベット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; }
