CodeForces 937D Sleepy Game

题意：Petya and Vasya 在玩移动旗子的游戏，谁不能移动就输了。 Vasya在订移动计划的时候睡着了，然后Petya 就想趁着Vasya睡着的时候同时定下策略，如果可以赢得话输出Win 并输出路径，如果步数在达到1e6的情况下，就认定为平局，输出Draw，如果输的话就输出lost。

题解：每个点以奇偶的步数通过就能确定是否为赢，如果偶数步走到这个点，那么下次再偶数走过这个点，那么这个点上次通过的点的步数奇偶就不变了，就不需要走了。

可以用Tarjian 缩环，然后标记一下成环的点，这样如果走路的时候访问到这个点，那么就算至少也可以到达平局。

然后在走到没有路的点，然后判断一下奇偶就好了。

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstdio>
 6 using namespace std;
 7 const int N = 1e6+10;
 8 struct Node{
 9     int to;
10     int nt;
11 }e[N];
12 int tot = 0;
13 int head[N], vis[N], ans[N], last[N];
14 int instack[N], low[N], dfn[N], vvis[N], Stack[N];
15 int ccnt = 0, top = 0;
16 void add_edge(int u, int v){
17     e[tot].to = v;
18     e[tot].nt = head[u];
19     head[u] = tot++;
20 }
21 void Tar(int u){
22     instack[u] = 1, vvis[u] = 1;
23     low[u] = dfn[u] = ccnt++;
24     Stack[++top] = u;
25     for(int i = head[u]; ~i; i = e[i].nt){
26         int v = e[i].to;
27         if(!vvis[v]) Tar(v);
28         if(instack[v]) low[u] = min(low[v], low[u]);
29     }
30     if(low[u] == dfn[u]){
31         if(Stack[top] == u){
32             top--;
33             instack[u] = 0;
34             return;
35         }
36              while(1){
37             int v = Stack[top--];
38             vvis[v] = -1;
39             instack[v] = 0;
40             if(v == u) break;
41         }
42     }
43 }
44 bool draw = false, win = false;
45 int ans_cnt = 0;
46 int max_n = 1e6;
47 void dfs(int u, int cnt){
48     if(win) return ;
49     if(cnt >= max_n) {draw = true; return;}
50     if(vis[u] == -1) return;
51     if(vvis[u] == -1) draw = true;
52     vis[u]++;
53     ans[cnt] = u;
54     if(vis[u] == 1) last[u] = cnt;
55     if(vis[u] > 1 && (cnt-last[u])%2 == 0) {return ;}
56     if(vis[u] > 1 && (cnt-last[u])%2 == 1)
57         {vis[u] = -1;}
58     if(head[u] == -1 && cnt&1) {win = true; ans_cnt = cnt ; return;}
59     for(int i = head[u]; ~i; i = e[i].nt){
60         dfs(e[i].to, cnt+1);
61     }
62 }
63 int main(){
64     int n, m;
65     scanf("%d%d",&n,&m);
66     int t, v;
67     memset(head, -1, sizeof(head));
68     memset(last, -1, sizeof(last));
69     for(int i = 1; i <= n; i++){
70         scanf("%d",&t);
71         for(int j = 1; j <= t; j++){
72             scanf("%d",&v);
73             add_edge(i,v);
74         }
75     }
76     for(int i = 1; i <= n; i++)
77         if(!vvis[i]) Tar(i);
78     scanf("%d",&v);
79     dfs(v,0);
80     if(win){
81         printf("Win
");
82         for(int i = 0; i <= ans_cnt; i++)
83             printf("%d%c",ans[i]," 
"[i == ans_cnt]);
84     }
85     else if(draw)
86         printf("Draw
");
87     else printf("Lose
");
88     return 0;
89 }