POJ 1300 - Door Man

http://poj.org/problem?id=1300

概要

N 個の部屋をいくつかのドアが繋いでいる．

M 番目の部屋からスタートしてドアを閉めてゆく．最初，すべてのドアは開いている．このとき，以下の条件を満たすようなパスが存在するかどうかを答える．また，存在する場合は閉めるドアの数も答える．

ドアを通過したら，そのドアは必ず閉める
閉じているドアを開けない
0 番目の部屋にすべてのドアを閉めた状態で到達する

制約

1 <= N <= 20

解法

条件からドアは全て閉めるので，閉めたドアの数 = ドアの数．

M からスタートして 0 で終わるパスが存在するかどうかは，

M = 0 のときは，次数が奇数な頂点が無いとき(オイラーグラフ)に限って YES
M != 0 のときは，次数が奇数な頂点がちょうど2つあり(準オイラーグラフ)，いずれかが頂点 0 のときに限って YES

で判断する．

N の制約が異常に小さいので本当にこれだけでいいのか心配だった．それと入力がめんどくさかった．

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   string line;
 9   while (getline(cin, line) && line != "ENDOFINPUT") {
10     int M, N;
11     {
12       istringstream iss(line);
13       iss >> line >> M >> N;
14     }
15     vector<int> deg(N, 0);
16     int c = 0;
17     for (int i = 0; i < N; i++) {
18       getline(cin, line);
19       istringstream iss(line);
20       int v;
21       while (iss >> v) {
22         ++deg[i];
23         ++deg[v];
24         ++c;
25       }
26     }
27     getline(cin, line);
28 
29     int odd[2];
30     int sz = 0;
31     for (int i = 0; i < N; i++) {
32       if (deg[i] % 2 == 1) {
33         if (sz > 2) {
34           ++sz;
35         } else {
36           odd[sz++] = i;
37         }
38       }
39     }
40 
41     if (sz > 2) {
42       cout << "NO" << endl;
43     } else if (M == 0) {
44       if (sz == 0) {
45         cout << "YES " << c << endl;
46       } else {
47         cout << "NO" << endl;
48       }
49     } else {
50       if (sz == 2 && (odd[0] == 0 || odd[1] == 0)) {
51         cout << "YES " << c << endl;
52       } else {
53         cout << "NO" << endl;
54       }
55     }
56   }
57   return 0;
58 }