Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <set>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <stdio.h>
- #include <cmath>
- #include <sstream>
- #include <algorithm>
- #include <iomanip>
- #define ll long long
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define vi vector<int>
- #define vl vector<long long>
- #define sz size()
- #define x first
- #define y second
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- using namespace std;
- string a[1010];
- int T, n, st, ft, degin[100], degout[100], deleted[1010];
- vi g[1010];
- vector<pii> edges;
- char ch[30];
- stack<int> S;
- vector<string> words[100][100];
- bool euler_check() {
- for(int i = 1; i <= 26; i++) {
- if(degin[i] - degout[i] == 1) {
- if(ft == 0) ft = i;
- else return false;
- } else if(degin[i] - degout[i] == -1) {
- if(st == 0) st = i;
- else return false;
- }
- }
- if((st == 0 && ft != 0) || (st != 0 && ft == 0)) return false;
- edges.pb(mp(ft, st));
- g[ft].pb(edges.sz - 1);
- words[ft][st].pb("###");
- return true;
- }
- vi find_euler_path() {
- S.push(st);
- vi ans;
- while(!S.empty()) {
- int v = S.top();
- for(int i = 0; i < g[v].sz; i++) {
- int ind = g[v][i];
- int to = edges[ind].s;
- if(!deleted[ind]) {
- S.push(to);
- deleted[ind] = 1;
- break;
- }
- }
- if(v == S.top()) {
- S.pop();
- ans.pb(v);
- }
- }
- return ans;
- }
- void clear() {
- for(int i = 1; i <= 1000; i++) {
- g[i].clear();
- }
- for(int i = 1; i <= 26; i++) {
- degin[i] = degout[i] = 0;
- for(int j = 1; j <= 26; j++) {
- words[i][j].clear();
- }
- }
- edges.clear();
- st = ft = 0;
- }
- void solve(int cs) {
- clear();
- scanf("%d", &n);
- for(int i = 1; i <= n; i++) {
- scanf("%s", ch);
- a[i] = ch;
- }
- for(int i = 1; i <= n; i++) {
- edges.pb(mp(a[i][0] - 'a' + 1, a[i][a[i].sz - 1] - 'a' + 1));
- g[a[i][0] - 'a' + 1].pb(edges.sz - 1);
- degin[a[i][a[i].sz - 1] - 'a' + 1]++;
- degout[a[i][0] - 'a' + 1]++;
- words[a[i][0]][a[i][a[i].sz - 1]].pb(a[i]);
- }
- printf("Case %d: ", cs);
- if(!euler_check()) {
- printf("No\n");
- return;
- }
- vi v = find_euler_path();
- reverse(v.begin(), v.end());
- vector<string> ans;
- for(int i = 0; i < v.sz; i++) {
- cout << char(v[i] + 'a' - 1) << " ";
- }
- }
- int main() {
- //freopen("", "r", stdin);
- //freopen("", "w", stdout);
- scanf("%d", &T);
- for(int i = 1; i <= T; i++) {
- solve(i);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement