FLIGHT GAME

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 41   Accepted Submission(s) : 10

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

越前龙马跟手冢国光pk飞行棋，但由于两人棋（yun）力(qi)相当，一直未能分出胜负，所以他们决定修改飞行棋的规则继续战斗。

他们将棋子由多个改成了一个，即两人轮流移动一个棋子，棋子初始时放在固定起点处，每次移动一格，龙马先走，谁先不能移动就算输，樱乃还是一如既往的支持越前，但还是心有担忧，棋盘可以看成一个有向无环图，现告诉你棋盘以及起点位置，假设龙马和手冢都选择最优策略，问越前能否赢的这场

Input

多组数据，每组数据的第一行三个数1<=n<=100,1<=m<=1000,1<=st<=n表示点数，边数，起点位置。

接下来m行给定棋盘，每行两个数x,y表示x可以移动到y，保证棋盘符合一个有向无环图，且节点编号。

Output

每组数据输出一行，若越前胜利输出”Yes”,否则输出”No”.

Sample Input

4 4 11 21 32 43 4

Sample Output

No

Author

yanglei9211

 

某个人出的题，不过觉得还有点意思，于是就写一下解题报告

题意是中文，应该算是博弈题吧，不过要用搜索解决，应为数据不大，可以直接遍历整个图。思想也不难，不过也想了挺久的，主要在判断走到某个根节点时谁胜谁负，然后处理一下子节点=0，=1，>1的情况就行了。

1 //62 MS    264 KB    Visual C++ 2 #include
     
       3 #include
      
        4 using namespace std; 5 vector
       
        V[105]; 6 int dfs(int u,int cnt) 7 { 8     int m=V[u].size(); 9     if(m==0) return cnt&1;10     if(m==1) return dfs(V[u][0],cnt+1);11     int flag=cnt&1;12     for(int i=0;i