分析
这个题乍一看有点像之前在CF上做过的一道DP，也是两个人下棋，但是写着写着觉得不对···这个题是的最优策略只是player 1
如果有环则是draw，可以DFS的时候顺便判环（拓扑排序的方法）,设dp(i,k) (k=0.1)当前在点i，我是先手（后手）是赢还是输
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 7 using namespace std; 8 const int maxn=100000+10; 9 vector<int>G[maxn]; 10 int n,m,s; 11 int Next[maxn][2]; 12 int vis[maxn][2],dp[maxn][2]; 13 bool cir=0; 14 int dfs(int u,int k){ 15 if(G[u].size()==0){ 16 return k==1; 17 } 18 if(vis[u][k]==2)return dp[u][k]; 19 vis[u][k]=1;bool ans=0; 20 int v; 21 for(int i=0;i<G[u].size();i++){ 22 v=G[u][i]; 23 if(vis[v][k^1]==1){ 24 cir=1; 25 continue; 26 } 27 if(dfs(v,k^1)){ 28 ans=1; 29 Next[u][k]=v; 30 break; 31 } 32 } 33 vis[u][k]=2; 34 dp[u][k]=ans; 35 return ans; 36 } 37 void print(int u,int k){ 38 printf("%d ",u); 39 if(Next[u][k]) 40 print(Next[u][k],k^1); 41 } 42 int main(){ 43 scanf("%d%d",&n,&m); 44 int c,x; 45 for(int i=1;i<=n;i++){ 46 scanf("%d",&c); 47 for(int j=1;j<=c;j++){ 48 scanf("%d",&x); 49 G[i].push_back(x); 50 } 51 } 52 scanf("%d",&s); 53 if(dfs(s,0)){ 54 printf("Win "); 55 print(s,0); 56 }else if(cir){ 57 printf("Draw"); 58 }else 59 printf("Lose"); 60 return 0; 61 }