1045
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define MP make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" vvi E; vi C; vi CC; int dfs(int v) { CC[v] = 1; C[v] = 0; int r = 10000; for(int i = 0; i < E[v].size(); i++) { if(CC[E[v][i]] == 0) { dfs(E[v][i]); if(C[E[v][i]] == 0) { C[v] = 1; r = min(r, E[v][i]); } } } if(r == 10000) { return v; } return r; } int main(void) { #ifndef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int N; int v; cin >> N >> v; E.resize(N+1); C.resize(N+1); CC.resize(N+1); for(int i = 0 ; i < N - 1 ;i++) { int a,b; cin >> a >> b; E[a].pb(b); E[b].pb(a); } int u = dfs(v); if(C[v] == 1) { cout << "First player wins flying to airport " << u << endl; } else { cout << "First player loses" << endl; } return 0; }
page revision: 0, last edited: 12 May 2008 11:34