結果

問題 No.2418 情報通だよ！Nafmoくん
ユーザー eq_Keq_K
提出日時 2023-08-12 13:45:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 9,587 bytes
コンパイル時間 2,648 ms
コンパイル使用メモリ 206,624 KB
実行使用メモリ 17,324 KB
最終ジャッジ日時 2024-11-14 12:21:28
合計ジャッジ時間 4,527 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 75 ms
15,604 KB
testcase_04 AC 23 ms
14,124 KB
testcase_05 AC 45 ms
7,552 KB
testcase_06 AC 54 ms
14,848 KB
testcase_07 AC 47 ms
6,816 KB
testcase_08 AC 56 ms
17,324 KB
testcase_09 AC 59 ms
8,832 KB
testcase_10 AC 74 ms
14,116 KB
testcase_11 AC 66 ms
13,428 KB
testcase_12 AC 45 ms
11,576 KB
testcase_13 AC 21 ms
6,816 KB
testcase_14 AC 39 ms
9,216 KB
testcase_15 AC 39 ms
6,820 KB
testcase_16 AC 72 ms
11,264 KB
testcase_17 AC 20 ms
6,816 KB
testcase_18 AC 42 ms
13,148 KB
testcase_19 AC 19 ms
13,440 KB
testcase_20 AC 43 ms
6,820 KB
testcase_21 AC 26 ms
7,552 KB
testcase_22 AC 25 ms
6,816 KB
testcase_23 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
#define _GLIBCXX_DEBUG
//*/
#include <bits/stdc++.h>
/*
#include <atcoder/all>
using namespace atcoder;
//*/
using namespace std;
#define dbl double
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define tl3 tuple<ll,ll,ll>
#define vi vector<int>
#define vc vector<char>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vvb vector<vector<bool>>
#define vvl vector<vector<ll>>
#define vvvi vector<vector<vector<int>>>
#define vvvc vector<vector<vector<char>>>
#define vvvl vector<vector<vector<ll>>>
#define vvvvi vector<vector<vector<vector<int>>>>
#define vvvvc vector<vector<vector<vector<char>>>>
#define vvvvl vector<vector<vector<vector<ll>>>>
#define vpi vector<pii>
#define vpl vector<pll>
#define prq priority_queue
#define prq2 priority_queue<ll,vl, greater<ll>>
#define seti set<int>
#define setl set<ll>
#define quel queue<ll>
#define pb push_back
#define ps push
#define ins insert
#define rev reverse
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()
#define forv(i,V) for(const auto& i:V)
#define rep(i,n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,j,n) for (ll i = (ll)(j);i < (ll)(n);i++)
#define rep2(i,n) for(ll i=(ll)(n-1);i>=0ll;i--)
#define repi2(i,n,j) for(ll i=(ll)(n-1);i>=(ll)(j);i--)
#define faster ios::sync_with_stdio(false);std::cin.tie(nullptr);
const double PI=3.14159265358979323846;
vl dxs = {1, 0, -1, 0};
vl dys = {0, 1, 0, -1};
ll max(int a,ll b){return max((ll)a,b);}
ll max(ll a,int b){return max((ll)b,a);}
ll min(int a,ll b){return min((ll)a,b);}
ll min(ll a,int b){return min((ll)b,a);}
ll gcd(ll a,ll b){if(b==0){return a;}else{return gcd(b,a%b);}}
ll lcm(ll a,ll b){return (a/gcd(a,b))*b;}
ll indexlb(vl &v,ll x){auto it=lb(all(v),x);ll index=it-v.begin();return index;}
ll indexub(vl &v,ll x){auto it=ub(all(v),x);ll index=it-v.begin();return index;}
ll setlb(setl &s,ll x){auto it=s.lb(x); return *it;}//番目ではなく要素が返ってくる
ll setub(setl &s,ll x){auto it=s.ub(x); return *it;}//番目ではなく要素が返ってくる
void setpre(double d,ll x){cout<<fixed<<setprecision(x)<<d<<endl;}
void ldsetpre(ld d,ll x){cout<<fixed<<setprecision(x)<<d<<endl;}
template <typename T>
void output(vector<T> &A) {rep(i,A.size()){cout<<A[i];if(i!=A.size()-1){cout<<" ";}else{cout<<endl;}}}
template <typename T>
void cinvec(vector<T> &A){rep(i,A.size()) cin>>A[i];}
template <typename T>
void coutvece(vector<T> &A){for(ll i=0;i<A.size();i++) cout <<A[i]<<endl;}
template <typename T>
bool chmin(T &a,const T &b){if(b<a){a=b; return 1;} return 0;}
template <typename T>
bool chmax(T &a,const T &b){if(b>a){a=b; return 1;} return 0;}
void yesno(bool i){if(i)cout<<"yes"<<endl;else cout<<"no"<<endl;}
void YesNo(bool i){if(i)cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void YESNO(bool i){if(i)cout<<"YES"<<endl;else cout<<"NO"<<endl;}
ll suretu_sum(vl a){//数列の要素の和
    ll n=a.size();
    ll res=0;
    rep(i,n){
        res+=a[i];
    }
    return res;
}
bool isprime(ll n){//素数判定
    if(n<2) return false;
    else if(n==2) return true;
    else if(n%2==0) return false;
    double sqrtn=sqrt(n);
    for(int i=3;i<=sqrtn;i+=2){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
ll modinv(ll a,ll m){//mod m上でのaの逆元
    ll b=m,u=1,v=0;
    while(b){
        ll t=a/b;
        a-=t*b; swap(a,b);
        u-=t*v; swap(u,v);
    }
    u%=m;
    if(u<0) u+=m;
    return u;
}
ll modwari(ll a,ll b,ll m){//mod m上でのa/b
    ll ans=a*modinv(b,m)%m;
    return ans;
}
ll modpow(ll a,ll n,ll mod) {
    ll res=1;
    while(n>0) {
        if(n&1) res=(res*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
vl factt,invv,fact_inv;
void combjyunbi(ll size,ll mod){
    factt.resize(size+5);
    fact_inv.resize(size+5);
    invv.resize(size+5);
    factt[0]=factt[1]=1;
    fact_inv[0]=fact_inv[1]=1;
    invv[1]=1;
    repi(i,2,size+5){
        factt[i]=factt[i-1]*i%mod;
        invv[i]=mod-invv[mod%i]*(mod/i)%mod;
        fact_inv[i]=fact_inv[i-1]*invv[i]%mod;
    }
}
//combjyunbiしてから！！！
ll combmod(ll n,ll k,ll mod){
    return factt[n]*(fact_inv[k]*fact_inv[n-k]%mod)%mod;
}
ll combmod2(ll n,ll k,ll mod){
    ll ans=1;
    repi(i,1,k+1){
        ans*=modwari(n-i+1,i,mod);
        ans%=mod;
    }
    return ans;
}
//nが大きく、kが小さい場合(計算量はO(k))
struct edge {
    ll from;   //辺の始点
    ll to;     //辺の終点
    ll leng;   //辺の重み
};
struct yukoedge{
    ll to;
};
using Graph =vvl;
using Graph2=vector<vector<edge>>;
using Graph3=vector<vector<yukoedge>>;//.pb({x})で作成
vl topo_sort(const Graph3 &G){//bfs できない場合は返り値のsize≠n
    vl ans;
    ll n=G.size();
    vl ind(n);// ind[i]: 頂点iに入る辺の数(次数)
    rep(i,n){//count index
        forv(e,G[i]){
            ind[e.to]++;
        }
    }
    quel que;//辞書順最小が欲しかったらprq2にする
    rep(i,n){//次数が0の点
        if(ind[i]==0){
            que.push(i);
        }
    }
    while(!que.empty()){//bfs
        ll now=que.front();
        ans.pb(now);
        que.pop();
        forv(e,G[now]){
            ind[e.to]--;
            if(ind[e.to]==0) {
                que.push(e.to);
            }
        }
    }
    return ans;
}
vl sieve(ll n){
//fast_soinsuの前処理 O(NloglogN)
//vl min_factor=sieve(1e6)などでコピー
    vl min_factor(n+1);
    rep(i,n+1) min_factor[i] = i;
    for(ll i=2;i*i<=n;i++){
        if(min_factor[i]==i){
            for(ll j=2;i*j<= n;j++){
                if(min_factor[i*j]>i){
                    min_factor[i*j]=i;
                }
            }
        }
    }
    return min_factor;
}
vl fast_soinsu(const vl &min_factor,ll m){
//N以下の正整数すべてを素因数分解するときに有効
//vl min_factor=sieve(1e6);で前計算 O(NloglogN)
//vl g=soinsu(min_factor,i);でコピー
//本計算の計算量は O(logN)
    vl ans;
    while(m>1){
        ans.pb(min_factor[m]);
        m/=min_factor[m];
    }
    return ans;
}
vector<pll> factorize(ll n){//素因数分解　{因数,乗数}
    vector<pll> ans;
    for(ll a=2;a*a<=n;a++){
        if(n%a!=0) continue;
        ll ex=0;
        while(n%a==0){
            ex++;
            n/=a;
        }
        ans.pb({a,ex});
    }
    if(n!=1) ans.push_back({n, 1});
    return ans;
}
vl divisor(ll n){//約数列挙(sqrt(n))
    vl ret;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            ret.push_back(i);
            if(i*i!=n) ret.push_back(n/i);
        }
    }
    sort(all(ret));
    return ret;
}
vector<pair<ll,char>> rle(string s){//ランレングス圧縮(数,文字)
    ll n=s.length();
    vector<pair<ll,char>> res;
    char pre=s[0];
    ll cnt=1;
    repi(i,1,n) {
        if(pre!=s[i]){
            res.push_back({cnt,pre});
            pre=s[i];
            cnt=1;
        }
        else cnt++;
    }
    res.push_back({cnt,pre});
    return res;
}
vl bfs(Graph G,ll s){//始点sからの距離
    ll n=G.size();
    vl dist(n,-1);
    quel que;
    dist[s]=0;
    que.push(s);
    while (!que.empty()) {
        ll v=que.front();
        que.pop();
        forv(nv,G[v]) {
            if (dist[nv]!=-1) continue;
            dist[nv]=dist[v]+1;
            que.push(nv);
        }
    }
    return dist;
}

template <typename T>
vector<T> jyu_nasi(vector<T> a){//sortしてから！配列を重複なしにする
    a.erase(unique(all(a)),a.end());
    return a;
}

map<ll,ll> zaatu(vl &a,ll t){//O(NlogN) キーが返され、配列は圧縮済みのものになる
    map<ll,ll> poi;
    vl copy=a;
    sort(all(copy));
    copy=jyu_nasi(copy);
    vl res(a.size());
    rep(i,a.size()){
        if(t==0) poi[indexlb(copy,a[i])]=a[i];//t=0ならキーは圧縮、1ならキーは元の要素
        else poi[a[i]]=indexlb(copy,a[i]);
        res[i]=indexlb(copy,a[i]);
    }
    a=res;
    return poi;
}

vl ruisekiwa(vl a){//累積和とる
    ll n=a.size();
    vl res(n);
    res[0]=a[0];
    repi(i,1,n){
        res[i]=res[i-1]+a[i];
    }
    return res;
}

struct unionfind{
  vl p;
  unionfind(ll n):p(n,-1){}//rootなら-1*連結成分のサイズ
  ll root(ll x){
    if(p[x]<0){
      return x;
    } else{
      p[x]=root(p[x]);
      return p[x];
    }
  }
  ll size(ll x){
    return -p[root(x)];
  }
  bool same(ll x,ll y){
      return root(x)==root(y);
  }
  void merge(ll x,ll y){
    x=root(x);
    y=root(y);
    if(x==y) return;
    if(size(x)<size(y)){
        swap(x,y);
    }
    p[x]+=p[y];
    p[y]=x;
  }
  vvl groups(){
        ll _n=p.size();
        vl leader_buf(_n); vl group_size(_n);
        rep(i,_n){
            leader_buf[i]=root(i);
            group_size[leader_buf[i]]++;
        }
        vvl result(_n);
        rep(i,_n){
            result[i].reserve(group_size[i]);
        }
        rep(i,_n){
            result[leader_buf[i]].pb(i);
        }
        result.erase(
            remove_if(all(result),
                           [&](const vl& v) {return v.empty();}),
            result.end());
        return result;
    }
};

int main(){
    ll n,m;
    cin>>n>>m;
    unionfind UF(2*n);
    rep(i,m){
        ll a,b;
        cin>>a>>b;
        a--; b--;
        UF.merge(a,b);
    }
    vvl g=UF.groups();
    ll ans=0;
    rep(i,g.size()){
        ans+=g[i].size()/2;
    }
    cout<<n-ans<<endl;
}
0