BOJ 12534 - Battlefield (Large)

BOJ 12534 - Battlefield (Large)

오일러 회로 문제이다.

엣지 케이스들이 많아서 까다롭다.

void solve() {  
   int v, e;  
   cin >> v >> e;  
   vvi edges(v);  
   vi deg(v);  
   for (int i = 0, a, b; i < e; i++) {  
      cin >> a >> b;  
      edges[a].pb(b), edges[b].pb(a);  
      deg[a]++;  
      deg[b]++;  
   }  
   vi vis(v);  
   int component = 0, ans = 0;  
   int cycle = 0;  
   int path = 0;  
   for (int i = 0; i < v; i++) {  
      if (vis[i] || sz(edges[i]) == 0) continue;  
      component++;  
      vi group;  
      queue<int> q;  
      q.push(i);  
      vis[i] = 1;  
      while (sz(q)) {  
         int cur = q.front();  
         q.pop();  
         group.pb(cur);  
         for (int to: edges[cur]) {  
            if (!vis[to]) {  
               vis[to] = 1;  
               q.push(to);  
            }  
         }  
      }  
      int odd = 0;  
      for (int j: group) if (deg[j] % 2)odd++;  
      if (odd == 0) {  
         cycle++;  
      } else {  
         path++;  
         if (odd > 2)  
            ans += (odd - 2) / 2;  
      }  
   }  
   if (component > 1) {  
      ans += component;  
      cout << ans;  
   } else {  
      if (cycle || component == 0)  
         cout << ans;  
      else  
         cout << ans + 1;  
   }  
}  
  
signed main() {  
   fastio  
   int tt;  
   cin >> tt;  
   for (int t = 1; t <= tt; t++) {  
      cout << "Case #" << t << ": ";  
      solve();  
      cout << endl;  
   }  
   return 0;  
}