UVA 11927 - Games Are Important

option=com_onlinejudge&Itemid=8&page=show_problem&category=478&problem=3078&mosmsg=Submission+received+with+ID+13891171" target="_blank" style="">题目链接

题意：给定一个有向图，结点上有一些石头，两人轮流移动石头。看最后谁不能移动就输了，问先手还后手赢

思路：求出每一个结点的sg函数，然后偶数个石头结点能够不用考虑，由于对于偶数情况，总步数肯定能保证是偶数，所以仅仅要考虑奇数情况的结点

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <vector>

using namespace std;

const int N = 1005;

int n, m, sg[N];

vector<int> g[N];

int dfs(int u) {

	if (sg[u] != -1) return sg[u];

	if (g[u].size() == 0) return sg[u] = 0;

	bool vis[N];

	memset(vis, false, sizeof(vis));

 	for (int i = 0; i < g[u].size(); i++)

		vis[dfs(g[u][i])] = true;

	for (int i = 0; ; i++)

		if (!vis[i]) return sg[u] = i;

}

int main() {

	while (~scanf("%d%d", &n, &m) && n || m) {

		int u, v;

		memset(g, 0, sizeof(g));

		memset(sg, -1, sizeof(sg));

  		while (m--) {

  			scanf("%d%d", &u, &v);

  			g[u].push_back(v);

  		}

  		for (int i = 0; i < n; i++)

    		dfs(i);

  		int ans = 0, num;

  		for (int i = 0; i < n; i++) {

  			scanf("%d", &num);

  			if (num&1)

  				ans ^= sg[i];

    	}

    	printf("%s\n", ans == 0?

"Second":"First");

 	}

	return 0;

}