AOJ Kobutanukitsuneko

AOJ Kobutanukitsuneko

Kobutanukitsuneko | Aizu Online Judge

n個の文字列が与えられる。それらすべてを使ってしりとりができて、さらに最後に使った文字列の最後の文字が最初に使った文字列の最初の文字を一致させることが可能かどうかを判定する問題。x......yという文字列が与えられたときに、xからyへ有向辺を張り、できたグラフがオイラー閉路をなすかどうかを判定すれば良い。単にすべてを使ってしりとりができるか、という問題ならば、オイラー路をなすかどうかをみればよい。全体が連結であることを判定する必要もある。ワーシャルフロイドで最短経路を求めて連結性を確認したが、もっと単純にかけると思う。

Problem - D - Codeforces を解いたあとにやるとすごく易しく感じられる。スタートはどこからでもよく、オイラー路を出力する必要もないため、各ノードの相対次数のみ考えれば良い。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.14159265358979;

//#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; cin >> _x; return _x; }
      
#define N 26

signed main() { 
        int n;
        while (cin >> n) {
                if (n == 0) break;
                int deg[N] = { 0 };
                vi g[N];
                int start;
                bool yet = true;
                int d[N][N];
                rep(i, N) rep(j, N) d[i][j] = INF;
                rep(i, N) d[i][i] = 0;
                int used[N] = { 0 };
                rep(i, n) {
                        string s;
                        cin >> s;
                        char ss = s[0];
                        char tt = s.back();
                        g[ss - 'a'].pb(tt - 'a');
                        d[ss - 'a'][tt - 'a'] = d[tt - 'a'][ss - 'a'] = 1;
                        used[ss - 'a'] = used[tt - 'a'] = true;
                        if (yet) {
                                yet = false;
                                start = ss - 'a';//適当にスタート決める
                        }
                }
                rep(k, N) rep(i, N) rep(j, N) amin(d[i][j], d[i][k] + d[k][j]);//連結性確認のため
                bool f = true;
                rep(i, N) {
                        rep(j, N) {
                                if (used[i] && used[j]) {
                                        if (d[i][j] >= INF) {
                                                f = false;//連結でない
                                        }
                                }
                        }
                }
                rep(i, N) {//ノードiからみて
                        deg[i] += sz(g[i]);//自身の次数をカウント（自身の出次数）
                        rep(j, sz(g[i])) {
                                deg[g[i][j]] --;//行き先の次数をカウント（行き先の入次数）
                        }
                }
                rep(i, N) if (deg[i] != 0) f = false;//オイラー路でない
                puts(f ? "OK" : "NG");
        }
        return 0;
}