Aizu Online Judge 0086 - Patrol
解法
グラフとして考えます。
スタート地点とゴール地点においては次数が奇数、その他の交差点においては次数が奇数であれば良いです。
ソースコード
#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; }
感想
簡単な問題を埋めて自分を甘やかします。