結果

問題 No.2418 情報通だよ!Nafmoくん
ユーザー kakira9618
提出日時 2023-08-12 13:53:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 120 ms / 2,000 ms
コード長 2,397 bytes
コンパイル時間 888 ms
コンパイル使用メモリ 88,888 KB
実行使用メモリ 30,440 KB
最終ジャッジ日時 2024-11-14 12:22:28
合計ジャッジ時間 2,852 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <map>
using namespace std;
/*
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
*/
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define endl "\n"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]";
    return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}
ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
const int mod = 1e9 + 7;
struct UnionFind {
vector<int> data;
int gnum;
UnionFind(int size) : data(size, -1), gnum(size) {}
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
gnum--;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
int getGroupNum() {
return gnum;
}
vector<vector<int>> getGroups() {
map<int, vector<int>> G;
int N = data.size();
for (int i = 0; i < N; i++) {
G[root(i)].push_back(i);
}
vector<vector<int>> ret;
for(auto g : G) {
ret.push_back(g.second);
}
return ret;
}
};
void solve() {
int N, M; cin >> N >> M; N *= 2;
UnionFind uf(N);
for (int i = 0; i < M; i++) {
int a, b; cin >> a >> b; a--, b--;
uf.unionSet(a, b);
}
vector<vector<int>> G = uf.getGroups();
int cnt = 0;
for (int i = 0; i < G.size(); i++) {
if (G[i].size() % 2 == 1) cnt++;
}
cout << cnt / 2 << endl;
}
int main() {
#ifdef LOCAL_ENV
cin.exceptions(ios::failbit);
#endif
cin.tie(0);
ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(16);
solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0