这题搞了好久才搞过

题意

题目链接

注意，如果他有一种方案能够满足 “Win” 的条件，这时即使有环，结果仍然为 “Win” 。

解析

题目要求判断从起点走若干奇数步数能否到达一个无法走的点，即没有出度的点。因此我们只需要先标记下没有出度的点，再从起点开始 dfs ，判断有没有一次走到没有出度的点时步数为奇数步即可。

然而具体 dfs 的实现没有这么简单。首先，同一个点可能既可以奇数步到达，也可以偶数步到达，因此，我们需要用一个 $tag_{0/1}$ 数组记录，用 $0$ 表示该点能够用偶数步到达，用 $1$ 表示该点能够用奇数步到达。显然，起点是 $0$ 步，为偶数。

然后搜索时为了防止被环卡死以及浪费时间的情况，我们需要及时停止走重复的路线。容易知道，若下一个点与当前点奇偶性不同的情况已经被走过，我们就没有必要走了。

这样我们可以判断出 “Win” 的情况，那么在 “Win” 不成立时，我们只需要从起点跑一遍 tarjan 判断有无环即可。有即为 “Draw” ，反之为 “Lose”。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=2e5+5;
struct edge{
    int to,next;
}e[M];
int n,m,cnt,head[N],st;
int chu[N],ans[N],len;
bool tag[N][3],win;
inline void add(int x,int y){
    e[++cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
inline void dfs(int u,int check){//check ：0 偶数，1 奇数 
    tag[u][check]=true;
    ans[++len]=u;
    if(win) return;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(tag[v][check^1]) continue;//若下一个点与当前点奇偶性不同的情况已经被走过 
        if(!chu[v]&&(!check)){//若走到没有出度的点时步数为奇数步
            win=true;
            printf("Win\n");
            for(int j=1;j<=len;j++){
                printf("%d ",ans[j]);
            }   
            printf("%d",v);
        }
        dfs(v,check^1); 
        if(win) return;
    }
    len--;
}
int dfn[N],low[N],tot,cot;
bool insta[N],draw;
stack<int> s;
inline void paint(int u){
    s.pop();
    insta[u]=false;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++tot;
    s.push(u);
    insta[u]=true;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(insta[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        cot++;
        int CNT=1;
        while(s.top()!=u){
            paint(s.top());
            CNT++;
        }
        paint(u);
        if(CNT>=2) draw=true; 
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,k;i<=n;i++){
        scanf("%d",&k);
        chu[i]=k;
        for(int j=1,x;j<=k;j++){
            scanf("%d",&x);
            add(i,x);
        }
    }
    scanf("%d",&st);
    dfs(st,0);//标记奇偶 
    if(win)
        return 0;
    else{
        tarjan(st);//找环 
        if(draw){
            printf("Draw");
        }
        else printf("Lose");
    }
    return 0;
}