fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 1e5 + 5;
  5. vector<int> G[MX];
  6. bool dp[MX][2], mark[MX][2];
  7.  
  8. void init(int n){
  9. 	for(int i = 0; i < n; G[i].clear(), i++);
  10. }
  11.  
  12. bool solve(int node, int player){
  13. 	if(mark[node][player]) return dp[node][player];
  14. 	int next = 0;
  15. 	bool Ans = false;
  16.  
  17. 	for(int i = 0; i < G[node].size(); i++){
  18. 		next++;
  19. 		Ans |= solve(G[node][i], 1 - player);
  20. 	}
  21.  
  22. 	mark[node][player] = true;
  23. 	if(!next){
  24. 		if(player) return dp[node][player] = true;
  25. 	}
  26.  
  27. 	return dp[node][player] = Ans;
  28. }
  29.  
  30. int main() {
  31. 	int t, n, m, st, u, v;
  32. 	scanf("%d", &t);
  33. 	for(int i = 1; i <= t; i++){
  34. 		scanf("%d %d %d", &n, &m, &st);
  35. 		init(n);
  36. 		for(int j = 0; j < m; j++){
  37. 			scanf("%d %d", &u, &v); u--, v--;
  38. 			G[u].push_back(v);
  39. 		}
  40. 		memset(dp, false, sizeof(dp));
  41. 		memset(mark, false, sizeof(mark));
  42. 		bool Ans = solve(st - 1, 0);
  43. 		Ans ? printf("Case %d: Yes\n", i) : printf("Case %d: No\n", i);
  44. 	}
  45. 	return 0;
  46. }
  47.  
Success #stdin #stdout 0s 17976KB
comments (?)
stdin
copy 
1
4 4 1
1 2
2 4
2 3
3 4
stdout
copy 
Case 1: Yes
https://ideone.com/L7pxbT
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!