fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <bitset>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. const int MAXN = 2005;
  10.  
  11. // Używamy tablicy bitsetów dla szybkiej operacji XOR na wierszach macierzy sąsiedztwa
  12. bitset<MAXN> adj[MAXN];
  13. int state[MAXN]; // 0 lub 1
  14. bool processed[MAXN]; // Czy węzeł został już "usunięty" (przełączony)
  15.  
  16. int main() {
  17.     // Optymalizacja wejścia/wyjścia
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(NULL);
  20.  
  21.     int n, m;
  22.     if (!(cin >> n >> m)) return 0;
  23.  
  24.     string s;
  25.     cin >> s;
  26.  
  27.     // Kolejka do przechowywania węzłów, które trzeba przełączyć (stan 1)
  28.     queue<int> q;
  29.  
  30.     for(int i = 0; i < n; ++i) {
  31.         state[i] = s[i] - '0';
  32.         if (state[i] == 1) {
  33.             q.push(i);
  34.         }
  35.         processed[i] = false;
  36.     }
  37.  
  38.     for(int i = 0; i < m; ++i) {
  39.         int u, v;
  40.         cin >> u >> v;
  41.         --u; --v;
  42.         adj[u][v] = 1;
  43.         adj[v][u] = 1;
  44.     }
  45.  
  46.     vector<int> result;
  47.     result.reserve(n);
  48.  
  49.     while(!q.empty()) {
  50.         int u = q.front();
  51.         q.pop();
  52.  
  53.         // Jeśli węzeł był już przetworzony (mógł trafić do kolejki wielokrotnie), pomijamy go
  54.         if (processed[u]) continue;
  55.  
  56.         processed[u] = true;
  57.         result.push_back(u + 1);
  58.  
  59.         // Iterujemy po wszystkich sąsiadach u
  60.         // Ponieważ u jest usuwane, musimy zaktualizować wszystkich jego sąsiadów
  61.         for (int v = 0; v < n; ++v) {
  62.             if (u != v && adj[u][v] && !processed[v]) {
  63.                 // 1. Zmiana stanu sąsiada (0->1 lub 1->0)
  64.                 state[v] ^= 1;
  65.                 if (state[v] == 1) {
  66.                     q.push(v);
  67.                 }
  68.  
  69.                 // 2. Aktualizacja krawędzi (lokalne uzupełnienie)
  70.                 // Dla każdego sąsiada v węzła u, krawędzie między v a innymi sąsiadami u są odwracane.
  71.                 // Operacja XOR na bitsecie robi to hurtowo.
  72.                 adj[v] ^= adj[u];
  73.  
  74.                 // Czyścimy bity, które mogły zostać błędnie ustawione:
  75.                 // a) v nie może mieć krawędzi do samego siebie
  76.                 adj[v][v] = 0;
  77.                 // b) Połączenie z u jest już nieistotne (u jest processed), 
  78.                 // ale dla porządku bitsetu można je wyzerować (choć check !processed[v] to załatwia)
  79.                 adj[v][u] = 0; 
  80.             }
  81.         }
  82.     }
  83.  
  84.     // Weryfikacja końcowa
  85.     // Po zakończeniu procesu wszystkie nieprzetworzone węzły muszą być wyregulowane (0)
  86.     // i nie mogą mieć żadnych krawędzi.
  87.     bool possible = true;
  88.     for(int i = 0; i < n; ++i) {
  89.         if (!processed[i]) {
  90.             if (state[i] == 1) {
  91.                 possible = false;
  92.                 break;
  93.             }
  94.             // Sprawdzamy, czy zostały jakiekolwiek krawędzie do innych nieprzetworzonych węzłów
  95.             for (int j = 0; j < n; ++j) {
  96.                 if (!processed[j] && adj[i][j]) {
  97.                     possible = false;
  98.                     break;
  99.                 }
  100.             }
  101.             if (!possible) break;
  102.         }
  103.     }
  104.  
  105.     if (possible) {
  106.         cout << "TAK\n";
  107.         cout << result.size() << "\n";
  108.         for (size_t i = 0; i < result.size(); ++i) {
  109.             cout << result[i] << (i == result.size() - 1 ? "" : " ");
  110.         }
  111.         cout << "\n";
  112.     } else {
  113.         cout << "NIE\n";
  114.     }
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 3
1111
1 2
2 3
3 4
stdout
copy 
TAK
4
1 2 3 4
https://ideone.com/w9BkTQ
language:
C++14 (gcc 8.3)
created:
23 hours 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!