1303-C, *1600

Problem - C - Codeforces

 

 

풀이

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
string dfs(char head, map<char, set<char> >& edge)
{
    vector<int> visited(26);
    string ret = "";
    queue<char> q;
    q.push(head);
    visited[head-'a'] = 1;
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        ret = ret + cur;
        for(auto e: edge[cur]){
            if(visited[e-'a'] != 1){
                q.push(e);
                visited[e-'a'] = 1;
            }
        }
    }
 
    ooop(i, 26){
        if(visited[i] == 0){
            ret = ret + char(97+i);
        }
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
 
        if(s.size() == 1){
            string res = "";
            ooop(i, 26){
                res = res + char(97+i);
            }
            cout << "YES" << endl << res << endl;
            continue;
        }
 
        map<char, set<char> > edge;
        ooop(i, s.size()-1){
            edge[s[i]].insert(s[i+1]);
            edge[s[i+1]].insert(s[i]);
        }
 
        bool flag = true;
        char head = '0';
        for(auto [key, s]: edge){
            if(s.size() > 2) {
                flag = false;
                break;
            }
            if(s.size() == 1) head = key;
        }
 
        if(flag && (head != '0')) cout << "YES" << endl << dfs(head, edge) << endl;
        else cout << "NO" << endl;
 
    }
 
    return 0;
}cs