Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <queue>
- using namespace std;
- struct Pole{
- int number;
- set<int> neighbourhood;
- bool ifRed = false;
- bool ifGreen = false;
- };
- void changeQueue( queue<Pole *> greenQueue, queue<Pole *> redQueue, Pole **arr){
- while(greenQueue.size()!= 0 || redQueue.size() != 0){
- if(greenQueue.size() != 0){
- while (greenQueue.size()) {
- if(greenQueue.front()->neighbourhood.size() == 0){
- cout << 'WIN' << endl;
- return;
- }
- for (auto x : greenQueue.front()->neighbourhood) {
- if (arr[x]->ifRed == false) {
- arr[x]->ifRed = true;
- redQueue.push(arr[x]);
- }
- }
- greenQueue.pop();
- }
- }else if (redQueue.size() != 0) {
- while (redQueue.size()) {
- for (auto y : redQueue.front()->neighbourhood) {
- if (arr[y]->ifGreen == false) {
- arr[y]->ifGreen = true;
- greenQueue.push(arr[y]);
- }
- }
- redQueue.pop();
- }
- }else{
- return;
- }
- }
- }
- int main() {
- queue<Pole *> greenQueue;
- queue<Pole *> redQueue;
- unsigned t;
- cin >> t;
- for( int i =0; i<t; i ++ ){
- int n,m,s;
- cin >> n >> m >> s;
- Pole * arr = new Pole[n];
- for(int j = 0; j < n; j++){
- arr[j].number = j;
- }
- for(int k = 0; k < m; k++){
- int a, b;
- cin >> a >> b;
- arr[a].neighbourhood.insert(b);
- }
- greenQueue.push(&arr[s]);
- arr[s].ifGreen = true;
- cout << greenQueue.size()<< endl;
- changeQueue(greenQueue,redQueue,&arr);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement