Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. using namespace std;
  5.  
  6. vector <ll> pai;
  7.  
  8. ll find(ll x){
  9.     if(x==pai[x]) return x;
  10.     return pai[x] = find(pai[x]);
  11. }
  12.  
  13. void join(ll x, ll y){
  14.     x = find(x);
  15.     y = find(y);
  16.     pai[y] = x;
  17. }
  18.  
  19. int main(){
  20.     ll n;
  21.     scanf("%lld", &n);
  22.     pai.resize(n);
  23.     for(int i=0;i<n;i++) pai[i] = i;
  24.     ll cont=0;
  25.     map <ll, ll> appeared;
  26.    
  27.     vector<pair<ll, ll>> entrada;
  28.     ll nx = n;
  29.     while(nx--){
  30.         ll x, y;
  31.         scanf("%lld %lld", &x, &y);
  32.         entrada.pb({x,y});
  33.     }
  34.  
  35.     for(int i=0;i<entrada.size();i++){
  36.         for(int j=i+1;j<entrada.size();j++){
  37.             if(entrada[i].first==entrada[j].first || entrada[i].second==entrada[j].second){
  38.                 join(i, j);
  39.             }
  40.         }
  41.     }
  42.     for(int i=0;i<n;i++){
  43.         //cout << find(i) << " ";
  44.         if(appeared.count(find(i))==0){
  45.             appeared[find(i)] = 1;
  46.             cont++;
  47.         }
  48.     }
  49.     //cout << endl;
  50.     printf("%lld\n", cont-1);
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement