結果

問題 No.2418 情報通だよ!Nafmoくん
ユーザー InTheBloom
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 () {
// -> UF
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);
}
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";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0