結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2024-03-05 14:16:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,267 bytes |
コンパイル時間 | 1,090 ms |
コンパイル使用メモリ | 89,332 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 12:25:58 |
合計ジャッジ時間 | 2,685 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream>#include <vector>using namespace std;class UnionFind {private:vector<int> par, size;public:UnionFind (int N) {par.resize(N);size.resize(N);for (int i = 0; i < N; i++) {par[i] = i;size[i] = 1;}}int root (int u) {if (par[u] == u) return u;return par[u] = root(par[u]);}void unite (int u, int v) {int l = root(u);int s = root(v);if (l == s) return;if (size[l] < size[s]) swap(l, s);size[l] += size[s];par[s] = l;}bool same (int u, int v) {return root(u) == root(v);}int groupsize (int u) {return size[u];}};int main () {// 余るのは常に連結成分数の端数だけ -> UFint 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);}int ans = 0;for (int i = 0; i < 2*N; i++) {if (UF.root(i) == i) ans += UF.groupsize(i) % 2;}ans /= 2;cout << ans << "\n";}