A funny game(1)

さて、TrisGさんも無事ACされたようなので、ここで私が最初に書いたコードを説明しておく。

たとえばこんな配置で、スタート空港を8番とする。とりあえず最初にすることは、爆破ｗ

スタート地点を消すと、そこに隣接する空港を根とする木ができる。あとはそれぞれの木に関してDFSで探索しながら勝ち負け判定を入れればおしまいだ。このアルゴリズムの良い点は、隣接空港をリストに入れてしまうので、隣接空港のリストをソートしておけば、勝ちパターンが見つかった時点で即座に探索を終了することが出来る。(今回はそれほど速度が求められる問題ではなかったので何もしていないが・・・)
勝ち負けの判定で注意する点は、たとえばこの例だと

6番からスタートすると、相手に3番に入られるから負け確定なのだが7番→9番と進むと、木が同じ形をしていても行動の選択権が自分にあるので、10番に入って勝ちになる。この問題の引っ掛けどころといえばコレに尽きるんじゃないかと思う。
というわけで、私は最初にこんなコードを書いてみた。

// 接続行列（まんま）

char c[1001][1001];

// スタート地点に隣接する空港を根とする

int root[999],rootCount=0;
int n,k; // n:空港数 k:スタート場所

int min=9999; // 最小の空港番号
// DFSを基本に探索しましょうかネ・・・

int dfs(k,node)

{

    // 一通りでも負けパターンがあれば0にセット

    int winAND = 1;

    // 一通りでも勝つ可能性があれば1にセット

    int winOR  = 0;
    int hit = 0; // 移動できる空港の数

    int i,t,win; // いろいろ
    for( i=1; i<=n; ++i)

    {

        if( c[k][i] )

        {

            c[k][i]=c[i][k]=0; // 爆破(｀ω´)

            

            t = dfs(i,node+1);

            winAND *= t;

            winOR += t;

            

            c[k][i]=c[i][k]=1; // 修復(´ω｀)
            ++hit; // 一箇所見つかりました

        }

    }
    // 基本的に負ける可能性があればダメです・・・

    win = winAND;
    // でも諦めないで！自分の番のときに

    // 勝つ可能性があるのなら、きっと勝てるわ！

    if( winAND==0 && node%2==0 && winOR ) win = 1;
    if( hit==0 ) // hit==0ということはもう移動できないね

    {

        if( node%2 )return 1; // 勝ったヨ！

        else return 0; // あー負け負け

    }

    else return win;

}
main(i,j,k)

{

    scanf("%d%d",&n,&k);

    for(;~scanf("%d%d",&i,&j);)

    {

        // スタート地点に隣接する空港をroot配列に登録

        if(i==k||j==k)

            root[rootCount++]=i==k?j:i;

        // 隣接してなければ接続行列に登録

        else

            c[i][j]=c[j][i]=1;

    }

    for(i=0;i<rootCount;++i){

        if(dfs(root[i],1))min=root[i]<min?root[i]:min;

    }
    if(min<9999)

        printf("First player wins flying to airport %d\n",min);

    else

        puts("First player loses");

}

てなわけで、問題は終わっているのだが相変わらずの短縮癖はどうしようもなく、只今249Bだ。
http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=2599&orderby=clen&language=-1
もうちょっと縮みそうな気がするんだけど、もういいかな。

追記：
100B台で通りそうなコードをSubmitしたら、消し去られた。私にはcheatコードが許されないようです。っていうか、明らかに監視されてる(;´д｀)