fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6.  
  7. typedef pair<int, int> ii;
  8. typedef vector<int> vi;
  9. typedef vector<ii> vii;
  10. typedef vector<vi> vvi;
  11. typedef vector<vii> vvii;
  12.  
  13. vvii adj; vi col;
  14. // 0 human, 1 parasite
  15.  
  16. int dfs1(int u, int c){
  17.     col[u] = c; int ans = c;
  18.     for(auto pp : adj[u]){
  19.         int v = pp.first, w = pp.second;
  20.  
  21.         if(col[v] == -1){
  22.             int jp = dfs1(v, c^w);
  23.             if(jp == -1) return -1;
  24.             ans += jp;
  25.         }else if(col[v] != (c^w)) return -1;
  26.     }
  27.     return ans;
  28. }
  29.  
  30. void clear_dfs(int u){
  31.     col[u] = -1;
  32.     for(auto pp : adj[u]){
  33.         int v = pp.first;
  34.  
  35.         if(col[v] != -1) clear_dfs(v);
  36.     }
  37.     return;
  38. }
  39.  
  40. int main(){
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.  
  44.     int T; cin >> T;
  45.     while(T--){
  46.         int N, Q; cin >> N >> Q;
  47.         adj.resize(N); col.resize(N, -1);
  48.  
  49.         vi cnt(N);
  50.         while(Q--){
  51.             int k, a, b; cin >> k >> a >> b;
  52.             if(k == 2) k = 0;
  53.             adj[a-1].push_back({b-1, k});
  54.             adj[b-1].push_back({a-1, k});
  55.         }
  56.  
  57.         int ans = 0;
  58.         for(int x = 0; x < N; x++){
  59.             if(col[x] != -1) continue;
  60.             int tmp = -1;
  61.             // set as 0
  62.             tmp = max(tmp, dfs1(x, 0));
  63.             clear_dfs(x);
  64.  
  65.             // set as 1
  66.             tmp = max(tmp, dfs1(x, 1));
  67.  
  68.             if(tmp == -1) {ans = -1; break;}
  69.             ans += tmp;
  70.         }
  71.  
  72.         cout << ans << "\n";
  73.  
  74.         adj.clear(); col.clear();
  75.  
  76.     }
  77.  
  78.  
  79.     return 0;
  80. }
Runtime error #stdin #stdout 0.01s 5504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HdCPNt
language:
C++14 (gcc 8.3)
created:
3 years 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!