Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define pb push_back
- using namespace std;
- vector <ll> pai;
- ll find(ll x){
- if(x==pai[x]) return x;
- return pai[x] = find(pai[x]);
- }
- void join(ll x, ll y){
- x = find(x);
- y = find(y);
- pai[y] = x;
- }
- int main(){
- ll n;
- scanf("%lld", &n);
- pai.resize(n);
- for(int i=0;i<n;i++) pai[i] = i;
- ll cont=0;
- map <ll, ll> appeared;
- vector<pair<ll, ll>> entrada;
- ll nx = n;
- while(nx--){
- ll x, y;
- scanf("%lld %lld", &x, &y);
- entrada.pb({x,y});
- }
- for(int i=0;i<entrada.size();i++){
- for(int j=i+1;j<entrada.size();j++){
- if(entrada[i].first==entrada[j].first || entrada[i].second==entrada[j].second){
- join(i, j);
- }
- }
- }
- for(int i=0;i<n;i++){
- //cout << find(i) << " ";
- if(appeared.count(find(i))==0){
- appeared[find(i)] = 1;
- cont++;
- }
- }
- //cout << endl;
- printf("%lld\n", cont-1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement