Submission #6071309

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ft first
#define sd second
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

vector<pair<int,int>> p;
vector<set<int>> x(100001),y(100001),z;
vector<bool> vx(100001),vy(100001);


void sy(int i,set<int>& s,set<int>& t);

void sx(int i,set<int>& s,set<int>& t){
    if(vx[i]) return;
    vx[i]=1;
    for(auto& j:x[i]){
        if(s.insert(j).sd){
            sy(j,s,t);
        }
    }
}

void sy(int i,set<int>& s,set<int>& t){
    if(vy[i]) return;
    vy[i]=1;
    for(auto& j:y[i]){
        if(t.insert(j).sd){
            sx(j,s,t);
        }
    }
}

ll slvx(int i){
    if(vx[i]) return 0;
    if(x[i].size()==1) return 0;
    set<int> s,t;
    t.insert(i);
    sx(i,s,t);
    return s.size()*t.size();
}

ll slvy(int i){
    if(vy[i]) return 0;
    if(y[i].size()==1) return 0;
    set<int> s,t;
    s.insert(i);
    sy(i,s,t);
    return s.size()*t.size();
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    p.resize(n);
    for(auto& i:p){
        cin>>i.ft>>i.sd;
        x[i.ft].insert(i.sd);
        y[i.sd].insert(i.ft);
    }
    ll ans=0;
    fr(i,n){
        ans+=slvx(p[i].ft)+slvy(p[i].sd);
    }
    fr(i,n){
        ans+=!vx[p[i].ft];
    }
    cout<<ans-n<<endl;
}

Submission Info

Judge Result