Advertisement
Guest User

Untitled

a guest
Jan 19th, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <queue>
  4.  
  5. using namespace std;
  6. struct Pole{
  7. int number;
  8. set<int> neighbourhood;
  9. bool ifRed = false;
  10. bool ifGreen = false;
  11. };
  12.  
  13. void changeQueue( queue<Pole *> greenQueue, queue<Pole *> redQueue, Pole **arr){
  14. while(greenQueue.size()!= 0 || redQueue.size() != 0){
  15. if(greenQueue.size() != 0){
  16. while (greenQueue.size()) {
  17. if(greenQueue.front()->neighbourhood.size() == 0){
  18. cout << 'WIN' << endl;
  19. return;
  20. }
  21. for (auto x : greenQueue.front()->neighbourhood) {
  22. if (arr[x]->ifRed == false) {
  23. arr[x]->ifRed = true;
  24. redQueue.push(arr[x]);
  25. }
  26. }
  27. greenQueue.pop();
  28. }
  29. }else if (redQueue.size() != 0) {
  30. while (redQueue.size()) {
  31. for (auto y : redQueue.front()->neighbourhood) {
  32. if (arr[y]->ifGreen == false) {
  33. arr[y]->ifGreen = true;
  34.  
  35. greenQueue.push(arr[y]);
  36. }
  37. }
  38. redQueue.pop();
  39. }
  40. }else{
  41. return;
  42. }
  43.  
  44.  
  45. }
  46.  
  47. }
  48.  
  49.  
  50.  
  51. int main() {
  52. queue<Pole *> greenQueue;
  53. queue<Pole *> redQueue;
  54. unsigned t;
  55. cin >> t;
  56. for( int i =0; i<t; i ++ ){
  57. int n,m,s;
  58. cin >> n >> m >> s;
  59. Pole * arr = new Pole[n];
  60. for(int j = 0; j < n; j++){
  61. arr[j].number = j;
  62. }
  63. for(int k = 0; k < m; k++){
  64. int a, b;
  65. cin >> a >> b;
  66. arr[a].neighbourhood.insert(b);
  67. }
  68. greenQueue.push(&arr[s]);
  69. arr[s].ifGreen = true;
  70. cout << greenQueue.size()<< endl;
  71. changeQueue(greenQueue,redQueue,&arr);
  72. }
  73.  
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement