結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-08-12 13:53:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 3,191 bytes |
コンパイル時間 | 1,942 ms |
コンパイル使用メモリ | 203,464 KB |
最終ジャッジ日時 | 2025-02-16 03:53:08 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#line 1 "template.hpp"#include<bits/stdc++.h>using ll = long long;#define REP(i, n) for(ll i = 0; (i) < ll(n); ++ (i))#define FOR(i, m, n) for(ll i = (m); (i) <= ll(n); ++ (i))#define REPR(i, n) for(ll i = ll(n) - 1; (i) >= 0; -- (i))#define FORR(i, m, n) for(ll i = ll(n); (i) >= ll(m); -- (i))#define ALL(x) x.begin(),x.end()#define INF (int)1e9#define LLINF (long long)1e18#define MOD (int)(1e9+7)#define MOD9 (int)998244353#define PI 3.141592653589#define PB push_back#define F first#define S second#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}#define Yes(T) {cout<<"Yes"<<endl; if(T) return 0;}#define No(T) {cout <<"No"<<endl; if(T) return 0;}#define YES(T) {cout<<"YES"<<endl; if(T) return 0;}#define NO(T) {cout <<"NO"<<endl; if(T) return 0;}#define Graph vector<vector<int> >#define CostGraph vector<vector<pair<int,ll> > >#define PII pair<int,int>#define PLL pair<ll,ll>#define VI vector<int>#define VL vector<ll>#define VVI vector<vector<int> >#define VVL vector<vector<ll> >#define VPII vector<pair<int,int> >#define VPLL vector<pair<ll,ll> >#define DDD fixed<<setprecision(10)#define PAD setfill('0')<<right<<setw(8)template <class T>inline bool chmin(T &a, T b) {if(a > b){ a = b; return true;}return false;}template <class T>inline bool chmax(T &a, T b) {if(a < b){a = b; return true;}return false;}struct input{int n;input() {}input(int n_) : n(n_){};template <class T>operator T(){T ret;std::cin >> ret;return ret;}template <class T>operator std::vector<T>() {std::vector<T> ret(n);REP(i,n) std::cin >> ret[i];return ret;}};template <class T>inline void printVec(std::vector<T> v){REP(i,v.size()){if(i) std::cout << " ";std::cout << v[i];} std::cout << std::endl;}using namespace std;#line 2 "data-structure/unionfind.hpp"struct UnionFind {vector<int> parent;vector<int> rank;UnionFind(int n) {init(n);}void init(int n) {parent.resize(n);rank.resize(n);for(int i = 0; i < n; ++i){parent[i] = i;rank[i] = 0;}}int getRoot(int x) {if(parent[x] == x) return x;return parent[x] = getRoot(parent[x]);}bool isSame(int x, int y) {return getRoot(x) == getRoot(y);}bool merge(int x, int y) {x = getRoot(x);y = getRoot(y);if(x == y) return false;if(rank[x] < rank[y]) swap(x, y);if(rank[x] == rank[y]) ++rank[x];parent[y] = x;return true;}vector<vector<int>> getGroups(){int n = rank.size();vector<vector<int>> rest(n), res;for(int i = 0; i < n; ++i) rest[getRoot(i)].push_back(i);for(int i = 0; i < n; ++i) if(rest[i].size()) res.push_back(rest[i]);return res;}};#line 3 "main.cpp"int main(){int n, m;cin >> n >> m;UnionFind uf(2*n);REP(i,m){int a, b;cin >> a >> b;uf.merge(a-1, b-1);}int cnt = 0;for(auto g: uf.getGroups()){if(g.size() % 2 == 1) cnt++;}cout << cnt / 2 << endl;}