結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-07-11 13:22:40 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 1,955 ms |
コンパイル使用メモリ | 127,488 KB |
実行使用メモリ | 20,096 KB |
最終ジャッジ日時 | 2024-11-14 12:20:01 |
合計ジャッジ時間 | 4,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream>#include <cassert>#include <map>#include <vector>using namespace std;struct UnionFind{vector<int> data;const uint __size;UnionFind(const int size = 0) noexcept : data(size, -1), __size(max(0, size)) {}inline int root(const int& x) {assert((uint)x < __size);if (data[x] < 0) return x;return data[x] = root(data[x]);}inline bool unite(const int& x, const int& y) {int rx = root(x), ry = root(y);if (rx == ry) return false;if (data[rx] > data[ry]) swap(rx, ry);data[rx] += data[ry];data[ry] = rx;return true;}inline bool same(const int& x, const int& y) { return root(x) == root(y); }inline int size(const int& x) { return -data[root(x)]; }};int main() {int n, m;cin >> n >> m;assert(1 <= n && n <= 100000);assert(0 <= m && m <= 100000);UnionFind uf(2 * n);for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;assert(1 <= a && a <= 2 * n);assert(1 <= b && b <= 2 * n);a -= 1;b -= 1;uf.unite(a, b);}map<int, vector<int>> group;for (int i = 0; i < 2 * n; ++i) {group[uf.root(i)].push_back(i);}int ans = 0;for (auto [_, g] : group) {if (g.size() % 2) {ans += 1;}}cout << ans / 2 << endl;return 0;}