結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2023-08-12 13:46:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 1,985 bytes |
コンパイル時間 | 1,675 ms |
コンパイル使用メモリ | 173,156 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-14 12:21:29 |
合計ジャッジ時間 | 3,366 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>const int INF=1<<30;// Union-Find 木class UnionFind{public:UnionFind() = default;// n 個の要素explicit UnionFind(size_t n): m_parents(n), m_sizes(n, 1){std::iota(m_parents.begin(), m_parents.end(), 0);}// i の root を返すint find(int i){if (m_parents[i] == i){return i;}// 経路圧縮return (m_parents[i] = find(m_parents[i]));}// a の木と b の木を統合void merge(int a, int b){a = find(a);b = find(b);if (a != b){// union by size (小さいほうが子になる)if (m_sizes[a] < m_sizes[b]){std::swap(a, b);}m_parents[b] = a;m_sizes[a] += m_sizes[b];}}// a と b が同じ木に属すかを返すbool connected(int a, int b){return (find(a) == find(b));}// i が属するグループの要素数を返すint size(int i){return m_sizes[find(i)];}private:// m_parents[i] は i の 親,// root の場合は自身が親std::vector<int> m_parents;// 属している要素数 (root 用)std::vector<int> m_sizes;};int main(){int n,m;std::cin >> n >> m;std::vector<std::pair<int,int>>V(m);UnionFind uf(2*n);for(auto&v:V){std::cin >> v.first >> v.second;--v.first;--v.second;uf.merge(v.first,v.second);}std::vector<int>sizes;for(int i=0;i<2*n;++i){if(uf.find(i)==i){sizes.push_back(uf.size(i));}}int remain=0;int ans=0;for(const auto&s:sizes){if(s%2==0)continue;if(remain==1){remain=0;}else{++remain;++ans;}}std::cout << ans << '\n';}