poj2599 A funny game---图的sg
#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>using namespace std;bool mat[1010][1010];bool flag[1010];int n;int dfs(int x){ flag[x]=false; for(int i=1;i<=n;i++) { if(mat[x][i]&&flag[i]) { flag[i]=false; if(dfs(i)==0) { flag[i]=true; return i; } flag[i]=true; } } return 0;}int main(){ int k; while(scanf("%d%d",&n,&k)!=EOF) { memset(mat,false,sizeof(mat)); memset(flag,true,sizeof(flag)); for(int i=0;i<n-1;i++) { int a,b; scanf("%d%d",&a,&b); mat[a][b]=mat[b][a]=true; } int d=dfs(k); if(d==0) puts("First player loses"); else printf("First player wins flying to airport %d\n",d); }}
#include<iostream>#include<cstdlib>#include<stdio.h>#include<vector>#include<algorithm>using namespace std;vector<int>v[1010];int g[22];int dfs(int x){ // cout<<"bug"<<endl; for(int i=0;i<v[x].size();i++) { int count=0; int f=v[x][i]; for(int j=0;j<v[x].size();j++) { int q=v[x][j]; g[count++]=q; for(int k=0;k<v[q].size();k++) { if(v[q][k]==x) { v[q].erase(v[q].begin()+k); break; } } v[x].erase(v[x].begin()+j); } if(dfs(f)==0) { for(int j=0;j<count;j++) { v[x].push_back(g[j]); v[g[j]].push_back(x); } return 1; } for(int j=0;j<count;j++) { v[x].push_back(g[j]); v[g[j]].push_back(x); } } return 0;}int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF) { for(int i=0;i<=n;i++) v[i].clear(); for(int i=0;i<n-1;i++) { int a,b; scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } sort(v[k].begin(),v[k].end()); bool flag=true; for(int i=0;i<v[k].size();i++) { if(dfs(v[k][i])==0) { flag=false; printf("First player wins flying to airport %d\n",v[k][i]); break; } } if(flag) puts("First player loses"); }}
