結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-06-21 01:12:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 909 bytes |
コンパイル時間 | 2,386 ms |
コンパイル使用メモリ | 202,960 KB |
最終ジャッジ日時 | 2025-02-14 23:45:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 2 WA * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct UnionFind {vector<int> data;UnionFind(int sz) { data.assign(sz, -1); }bool unite(int x, int y) {x = find(x), y = find(y);if (x == y) return (false);if (data[x] > data[y]) std::swap(x, y);data[x] += data[y];data[y] = x;return (true);}int find(int k) {if (data[k] < 0) return (k);return (data[k] = find(data[k]));}bool same(int x, int y) { return find(x) == find(y); }int size(int k) { return (-data[find(k)]); }};int main(void) {int ans = 0;int N, M;cin >> N >> M;UnionFind uf(2 * N);for (int i = 0; i < M; i++) {int a, b;cin >> a >> b;a--, b--;uf.unite(a, b);}map<int, int> parent;for (int i = 0; i < 2 * N; i++) {parent[uf.find(i)]++;}for (auto [x, y] : parent) {if (y & 1) {ans++;}}cout << ans << endl;}