AOJ 0225 Kobutanukitsuneko

誤読。閉路である必要があることを見落としていた。

解法

有向オイラー閉路を求める問題。 ぐぐると答えがでてくる。

連結性の確認を忘れないようにする。

実装

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    while (true) {
        int n; cin >> n;
        if (n == 0) break;
        bool g[26][26] = {};
        bool used[26] = {};
        int d[26] = {}; // relative degree
        repeat (i,n) {
            string s; cin >> s;
            int x = s.front() - 'a';
            int y = s.back()  - 'a';
            used[x] = true;
            used[y] = true;
            g[x][y] = true;
            d[x] += 1;
            d[y] -= 1;
        }
        repeat (k,26) { // warshall floyd
            repeat (i,26) {
                repeat (j,26) {
                    if (g[i][k] and g[k][j]) g[i][j] = true;
                }
            }
        }
        bool ans = true;
        repeat (i,26) {
            if (d[i] != 0) ans = false; // eulerlian cycle
        }
        repeat (i,26) if (used[i]) {
            repeat (j,26) if (used[j]) {
                if (not g[i][j]) {
                    ans = false; // not connected
                }
            }
        }
        cout << (ans ? "OK" : "NG") << endl;
    }
    return 0;
}