POJ 2599 - A funny game

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

概要

N 個の空港をいくつかのフライトが結んでいる．ある空港から別の空港へと行くパスは高々1つしか存在しない．

K 番目の空港からスタートして，二人のプレイヤーが交互に乗り継いで移動していく． 空港を発つ際にその空港を破壊するので，二度とその空港へは行けない． 移動できなくなったほうのプレイヤーが負け．

どちらのプレイヤーも完璧にゲームを進めたとき，先手が勝てる場合は先手が最初に進むべき空港を答え，先手が負ける場合は「First player loses」と答える．

制約

解法

与えられるのは木なので，K 番目の空港をルートとしてゲーム木探索の要領で探索すればいい．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 bool dfs(const vector<vector<bool> >& g, int n, vector<bool>& visited)
 6 {
 7   const int N = g.size();
 8   for (int i = 0; i < N; i++) {
 9     if (g[n][i] && !visited[i]) {
10       visited[i] = true;
11       if (!dfs(g, i, visited)) {
12         return true;
13       }
14     }
15   }
16   return false;
17 }
18 
19 int main()
20 {
21   int N, K;
22   cin >> N >> K;
23   --K;
24   vector<vector<bool> > g(N, vector<bool>(N, false));
25   for (int i = 0; i < N-1; i++) {
26     int a, b;
27     cin >> a >> b;
28     --a;  --b;
29     g[a][b] = g[b][a] = true;
30   }
31 
32   vector<bool> visited(N, false);
33   visited[K] = true;
34   for (int i = 0; i < N; i++) {
35     if (g[K][i] && !visited[i]) {
36       visited[i] = true;
37       if (!dfs(g, i, visited)) {
38         cout << "First player wins flying to airport " << i+1 << endl;
39         goto FINISH;
40       }
41     }
42   }
43   cout << "First player loses" << endl;
44 
45 FINISH:
46   return 0;
47 }
poj/2599.cc