2599 A funny game

問題概要

n個の空港がある。それぞれの空港はフライトによって直接または間接に行き来することができ、なおかつ行き来の仕方は一意に定まる。

二人のテロリストが次のようなゲームをする。
空港kから開始して、便に乗れなくなるまで以下を繰り返す。

• 今いる空港に爆弾を仕掛ける。
• 手番のテロリストが飛行機を選んで、二人で乗る。
• 空港を爆破する（以後その空港へはいけなくなる）

空港で乗れる便がなくなったときに手番のプレイヤーが負けである。
二人が最善の戦略を取るとき、先手後手のどちらが勝つかを出力せよ。

先手が勝つ場合、先手はどの空港を選ぶべきかを出力せよ。候補が複数ある場合もっとも小さい番号のものを出力せよ。

n≦1000を満たす。

解法

連結で、任意の二頂点のパスが一意に定まるという条件から、空港をグラフにすると木になることがわかる。

よって、前の頂点へは二度と戻れないので、単純に関数を再帰呼び出しして勝者を調べることができる。グラフが木であるため、関数に合流もない。

rec(c,p)を、現在空港cにいて、直前にpにいたときに先手が勝てるかどうかを返す関数とする。
cから行けるノードのうち、どれか一つでも先手が負けるものがあればrec(c,p)は先手勝ちとなる。
そうでないなら後手勝ちである。

ソースコード

int n,k,ans;
vector<vi> e;

bool rec(int c,int p){
	fr(i,e[c])if(*i!=p){
		if(!rec(*i,c)){
			if(c==k)ans=*i;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&k); k--;
	e.resize(n);
	rep(i,n-1){
		int a,b; scanf("%d%d",&a,&b);
		a--; b--;
		e[a].pb(b); e[b].pb(a);
	}
	if(rec(k,-1))printf("First player wins flying to airport %d\n",ans+1);
	else puts("First player loses");
	
	return 0;
}