n点m边的有向图，

如果  一个玩家能从起点出发，走奇数步后不能再行动，

　　输出Win

　　输出路径

否则如果  一个玩家能走无限步 

　　输出Draw

否则 

　　输出Lose

 

跑一遍dfs并判环

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 typedef long long LL; 7  8 const int maxn = 1e5 + 10; 9 vector
         
           G[maxn];10 11 int n, m;12 bool draw;13 bool out[maxn];14 bool dp[maxn][2];15 int vis[maxn][2], nxt[maxn][2];16 17 bool dfs(int x, int s) {18     if (!out[x]) return s == 1;19     if (vis[x][s] == 2) return dp[x][s];20     vis[x][s] = 1;21     bool flag = 0;22     for (int i = 0; i < G[x].size(); i++) {23         int to = G[x][i];24         if (vis[to][s ^ 1] == 1) {
   //注意不能为225             draw = 1;26             continue; 27         }28         if (dfs(to, s ^ 1)) {29             flag = 1;30             nxt[x][s] = to;31         }32     }33     vis[x][s] = 2;34     return dp[x][s] = flag;35 }36 37 void print(int x, int s) {38     printf("%d", x);39     if (nxt[x][s]) {40         printf(" ");41         print(nxt[x][s], s ^ 1);42     } else {43         puts("");44     }45 }46 47 48 49 int main() {50     scanf("%d%d", &n, &m);51     for (int i = 1; i <= n; i++) {52         int cnt;53         scanf("%d", &cnt);54         if (cnt) out[i] = 1;55         while (cnt--) {56             int to;57             scanf("%d", &to);58             G[i].push_back(to);59         }60     }61     int st;62     scanf("%d", &st);63     if (dfs(st, 0)) {64         puts("Win");65         print(st, 0);66     } else if (draw) {67         puts("Draw");68     } else {69         puts("Lose");70     }71 72     return 0;73 }