Aizu Online Judge 0086 - Patrol

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0086

日本語版があるので省略。

解法

グラフとして考えます。
スタート地点とゴール地点においては次数が奇数、その他の交差点においては次数が奇数であれば良いです。

ソースコード

#include <iostream>
#include <cstring>
using namespace std;

#define REP(i, x) for (int i = 0; i < (x); i++)
#define ALL(a) (a).begin(), (a).end()

const int MAX_N = 100 + 10;
int dim[MAX_N];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b;
    while (cin >> a >> b, !cin.eof()) {
        memset(dim, 0, sizeof(dim));
        dim[a - 1]++;
        dim[b - 1]++;

        while (cin >> a >> b, a | b) {
            dim[a - 1]++;
            dim[b - 1]++;
        }

        bool ok = true;
        REP (i, MAX_N) {
            if (i <= 1) ok &= dim[i] % 2;
            else ok &= !(dim[i] % 2);
        }
        if (ok) cout << "OK" << endl;
        else cout << "NG" << endl;
    }

    return 0;
}

感想

簡単な問題を埋めて自分を甘やかします。