fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //ACCEPTED CODE
  5.  
  6. typedef long long int ll;
  7. typedef unsigned long long int ull;
  8.  
  9. #define MOD 1000000007
  10. #define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  11.  
  12. ll par[300005], node, edge;
  13. map<ll, ll> mp;
  14.  
  15. ll find_par(ll r){
  16.     if(par[r] == r){
  17.         return r;
  18.     }
  19.     else return par[r] = find_par(par[r]);
  20. }
  21.  
  22. void union_find(ll x, ll y){
  23.     ll u = find_par(x);
  24.     ll v = find_par(y);
  25.  
  26.     if(u != v){
  27.         par[v] = u;
  28.     }
  29. }
  30.  
  31.  
  32. int main() {
  33.  
  34.     _FastIO;
  35.  
  36.     while(cin >> node >> edge){
  37.         for(int i = 1; i <= 300005; i++){
  38.             par[i] = i;
  39.         }
  40.         ll cnt = 0;
  41.         while(edge--){
  42.             ll x, y;
  43.             cin >> x >> y;
  44.  
  45.             if(mp[x] == 0){
  46.                 mp[x] = ++cnt;
  47.             }
  48.             if(mp[y] == 0){
  49.                 mp[y] = ++cnt;
  50.             }
  51.             union_find(mp[x], mp[y]);
  52.         }
  53.         ll ans = 0;
  54.         for(ll i = 1; i <= cnt; i++){
  55.             ll p = find_par(i);
  56.             if(p == i){
  57.                 ans++;
  58.             }
  59.         }
  60.         ans += (node-cnt);
  61.         cout << ans <<  endl;
  62.          mp.clear();
  63.     }
  64.  
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eLzUiU
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!