Advertisement
Josif_tepe

Untitled

Aug 27th, 2023
1,330
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn = 50005;
  7. int color[maxn];
  8. int invitation[maxn];
  9. vector<int> graph[maxn];
  10. int main(int argc, const char * argv[]) {
  11.     int n;
  12.     cin >> n;
  13.     for(int i = 0; i < n; i++) {
  14.         cin >> invitation[i];
  15.     }
  16.     int m;
  17.     cin >> m;
  18.     for(int i = 0; i < m; i++) {
  19.         int a, b;
  20.         cin >> a >> b;
  21.         a--; b--;
  22.         graph[a].push_back(b);
  23.         graph[b].push_back(a);
  24.     }
  25.     queue<int> q;
  26.     int initial_accepts = 0;
  27.     memset(color, 0, sizeof color);
  28.     for(int i = 0; i < n; i++) {
  29.         if(invitation[i] == 1) {
  30.             color[i] = 1;
  31.             q.push(i);
  32.             initial_accepts++;
  33.         }
  34.         if((int) graph[i].size() == 0) {
  35.             color[i] = 0;
  36.         }
  37.     }
  38.     while(!q.empty()) {
  39.         int node = q.front();
  40.         q.pop();
  41.         if(color[node] == 1) {
  42.             for(int neighbour : graph[node]) {
  43.                 if(color[neighbour] == 0) {
  44.                     color[neighbour] = 2;
  45.                     q.push(neighbour);
  46.                 }
  47.                 else if(color[neighbour] == 1) {
  48.                     color[neighbour] = 3;
  49.                     q.push(neighbour);
  50.                 }
  51.             }
  52.         }
  53.         else if(color[node] == 2) {
  54.             for(int neighbour : graph[node]) {
  55.                 if(color[neighbour] == 0) {
  56.                     color[neighbour] = 1;
  57.                     q.push(neighbour);
  58.                 }
  59.                 else if(color[neighbour] == 2) {
  60.                     color[neighbour] = 3;
  61.                     q.push(neighbour);
  62.                 }
  63.             }
  64.         }
  65.         else if(color[node] == 3) {
  66.             for(int neighbour : graph[node]) {
  67.                 if(color[neighbour] != 3) {
  68.                     color[neighbour] = 3;
  69.                     q.push(neighbour);
  70.                 }
  71.             }
  72.         }
  73.     }
  74.     for(int i = 0; i < n; i++) {
  75.         if(color[i] == 3) {
  76.             q.push(i);
  77.         }
  78.     }
  79.     vector<bool> visited(n, false);
  80.     while(!q.empty()) {
  81.         int node = q.front();
  82.         q.pop();
  83.         for(int neighbour : graph[node]) {
  84.             if(!visited[neighbour]) {
  85.                 visited[neighbour] = true;
  86.                 color[neighbour] = 3;
  87.                 q.push(neighbour);
  88.             }
  89.         }
  90.     }
  91.     int ones = 0, twos = 0, threes = 0;
  92.     for(int i = 0; i < n; i++) {
  93.         if(color[i] == 1) {
  94.             ones++;
  95.         }
  96.         else if(color[i] == 2) {
  97.             twos++;
  98.         }
  99.         else if(color[i] == 3) {
  100.             threes++;
  101.         }
  102.     }
  103.     int res1 = threes + max(ones, twos);
  104.     cout << max(res1, initial_accepts) << endl;
  105.     return 0;
  106. }
  107.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement