sgu - 520 - Fire in the Country

題意：n個點m條邊的無向連通圖，開始時結點1起火，火蔓延到其相鄰點需1天，開始時有個機器人也在結點1處，但機器人先走了，結點1才起火，Vladimir與Nikolay輪流控制這個機器人，機器人1天也只能移動到另一個相鄰點，最後誰不得不讓機器人走向火海誰就敗，輸出勝者。

——>>搜索中的博弈，策略：讓火跟著走，走進死胡同，下一天對手就沒得走了（若子狀態有一個先手必敗狀態，那麼現在這個狀態是先手必勝狀態）。

f[i]表示火蔓延到結點i要多少天。

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 1000 + 10;
int n, m, head[maxn], nxt[maxn<<1], u[maxn<<1], v[maxn<<1], ecnt, f[maxn];

void init(){
    for(int i = 1; i <= n; i++) head[i] = -1;
    ecnt = 0;
}

void addEdge(int uu, int vv){
    u[ecnt] = uu;
    v[ecnt] = vv;
    nxt[ecnt] = head[uu];
    head[uu] = ecnt;
    ecnt++;
}

void read(){
    int i, uu, vv;
    for(i = 0; i < m; i++){
        scanf("%d%d", &uu, &vv);
        addEdge(uu, vv);
        addEdge(vv, uu);
    }
}

void bfs(){
    queue<int> qu;
    while(!qu.empty()) qu.pop();
    f[1] = 1;
    qu.push(1);
    while(!qu.empty()){
        int u = qu.front(); qu.pop();
        for(int e = head[u]; e != -1; e = nxt[e]) if(!f[v[e]]){
            f[v[e]] = f[u] + 1;
            qu.push(v[e]);
        }
    }
}

void fire(){
    memset(f, 0, sizeof(f));
    bfs();
}

bool dfs(int u){
    for(int e = head[u]; e != -1; e = nxt[e]) if(f[v[e]] == f[u] + 1 && !dfs(v[e])) return 1;
    return 0;
}

int main()
{
    while(scanf("%d%d", &n, &m) == 2){
        init();
        read();
        fire();
        if(dfs(1)) printf("Vladimir\n");
        else printf("Nikolay\n");
    }
    return 0;
}