题目链接：http://codeforces.com/contest/937/problem/D
思路：其实就是看能不能找到一条为奇数并且出度为0的路线，找不到的话就看能不能找到成环的的。所以可以用一个数组存下到这个点奇偶路线情况，再用一个dfs染色判断是否成环。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cctype> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <sstream> #include<iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; const ll inff = 0x3f3f3f3f3f3f3f3f; #define FOR(i,a,b) for(int i(a);i<=(b);++i) #define FOL(i,a,b) for(int i(a);i>=(b);--i) #define REW(a,b) memset(a,b,sizeof(a)) #define inf int(0x3f3f3f3f) #define si(a) scanf("%d",&a) #define sl(a) scanf("%I64d",&a) #define sd(a) scanf("%lf",&a) #define ss(a) scanf("%s",a) #define mod int(1e9+7) #define lc (d<<1) #define rc (d<<1|1) #define Pll pair<ll,ll> #define P pair<int,int> #define pi acos(-1) int n,m,dp[100008][2],d[100008],pre[100008][2]; vector<int>g[100008],qw,sz; void dfs(int x,int y,int z) { dp[y][x&1]=1; pre[y][x&1]=z; for(int i=0;i<g[y].size();i++) { if(!dp[g[y][i]][(x+1)&1]) dfs(x+1,g[y][i],y); } } bool huan(int x) { d[x]=1; bool f=0; for(int i=0;i<g[x].size();i++) { if(d[g[x][i]]==1) f=1; else if(!d[g[x][i]]) f=huan(g[x][i]); if(f) return 1; } d[x]=2; return 0; } int main() { cin.tie(0); cin>>n>>m; int x,y,s; FOR(i,1,n) { si(x); if(!x) qw.push_back(i); while(x--) { si(y); g[i].push_back(y); } } si(s); dfs(0,s,0); for(int i=0;i<qw.size();i++) { if(dp[qw[i]][1]) { puts("Win"); int k=qw[i],z=1; while(pre[k][z]!=0) { sz.push_back(k); k=pre[k][z]; z=1-z; } sz.push_back(k); for(int j=sz.size()-1;j>=0;j--) cout<<sz[j]<<" "; puts(""); return 0; } } if(huan(s)) puts("Draw"); else puts("Lose"); return 0; }
