思路（copy自刘哥blog）：
dfs。
vis[u][0]==1表示u这个点能从s点偶数路径到达
vis[u][1]==1表示u这个点能从s点奇数路径到达
这个样就能保证dfs时每个点最多被访问2次
那么如果存在一个点u,vis[u][1]==1且u的出度为0，那么就存在能Win的方案
否则，dfs染色判环，如果存在从s点出发的环，就存在Draw的方案。注意这里，只要有环就行,应为前面已经判断过不会win
不然就是Lose
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <vector> using namespace std; const int maxn = 1e5+5; vector <int> mp[maxn],q; int pre[maxn][2]; int vis[maxn][2],vis2[maxn]; void dfs(int v,int s,int b) { if(vis[s][b]==1)return; vis[s][b] = 1; pre[s][b] = v; for(int i=0; i<mp[s].size();i++) { dfs(s,mp[s][i],b^1); } } bool hasloop(int s) { vis2[s]=1; bool f = false; for(int i=0; i<mp[s].size(); i++) { int tmp = mp[s][i]; if(vis2[tmp]==1)return true; else f=hasloop(tmp); if(f)return true; } vis2[s]=2; return false; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) { int c; scanf("%d",&c); while(c--) { int u; scanf("%d",&u); mp[i].push_back(u); } } int s; scanf("%d",&s); dfs(0,s,0); int u=0; for(int i=1;i<=n;i++) { if(vis[i][1]==1&&mp[i].size()==0) { u=i; break; } } if(u!=0) { printf("Win\n"); int b = 1; while(u != 0) //这里不要写成u！=s，因为可能会再经过s； { //cout<<"#"<<pre[u][1]<<"-0-"<<pre[u][0]<<endl; q.push_back(u); u=pre[u][b]; b^=1; } //printf("%d",s); for(int i=q.size()-1;i>0;i--) printf("%d ",q[i]); printf("%d\n",q[0]); } else { if(hasloop(s)) { printf("Draw\n"); } else printf("Lose\n"); } return 0; }
转载于:https://www.cnblogs.com/ckxkexing/p/8496474.html
相关资源：数据结构—成绩单生成器