fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <stack>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.  
  12.     int n, m;
  13.     if (!(cin >> n >> m)) return 0;
  14.     vector<int> s(n+1);
  15.     for (int i = 1; i <= n; ++i) cin >> s[i];
  16.     vector<vector<pair<int,int>>> adj(n+1);
  17.     vector<int> xu(m+1), yu(m+1);
  18.     for (int i = 1; i <= m; ++i) {
  19.         int x, y; cin >> x >> y;
  20.         xu[i] = x; yu[i] = y;
  21.         adj[x].push_back({y, i});
  22.         adj[y].push_back({x, i});
  23.     }
  24.  
  25.     vector<int> d(n+1);
  26.     for (int i = 1; i <= n; ++i) d[i] = 1 - s[i];
  27.  
  28.     vector<int> vis(n+1, 0), parent(n+1, 0), parentEdge(n+1, 0);
  29.     vector<int> ans; ans.reserve(m);
  30.  
  31.     for (int i = 1; i <= n; ++i) {
  32.         if (vis[i]) continue;
  33.         vector<int> st;
  34.         vector<int> order;
  35.         st.push_back(i);
  36.         vis[i] = 1;
  37.         parent[i] = 0;
  38.         parentEdge[i] = 0;
  39.         while (!st.empty()) {
  40.             int u = st.back();
  41.             st.pop_back();
  42.             order.push_back(u);
  43.             for (auto pr : adj[u]) {
  44.                 int v = pr.first, eid = pr.second;
  45.                 if (!vis[v]) {
  46.                     vis[v] = 1;
  47.                     parent[v] = u;
  48.                     parentEdge[v] = eid;
  49.                     st.push_back(v);
  50.                 }
  51.             }
  52.         }
  53.         int sumd = 0;
  54.         for (int v : order) sumd += d[v];
  55.         if (sumd % 2 == 1) {
  56.             cout << -1 << '\n';
  57.             return 0;
  58.         }
  59.         for (int idx = (int)order.size() - 1; idx >= 0; --idx) {
  60.             int u = order[idx];
  61.             if (parent[u] == 0) continue;
  62.             if (d[u] == 1) {
  63.                 ans.push_back(parentEdge[u]);
  64.                 d[u] ^= 1;
  65.                 d[parent[u]] ^= 1;
  66.             }
  67.         }
  68.     }
  69.  
  70.     cout << ans.size() << '\n';
  71.     for (size_t i = 0; i < ans.size(); ++i) {
  72.         if (i) cout << ' ';
  73.         cout << ans[i];
  74.     }
  75.     if (!ans.empty()) cout << '\n';
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XuUTAI
language:
C++14 (gcc 8.3)
created:
2 days 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!