Submission #6069126

---

Source Code Expand

#include <iostream>
#include <string>
#include <stdlib.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <map>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint n;
llint x[100005], y[100005];
UnionFind uf(100005);
vector<llint> vec[100005], vecx[100005];
set<llint> S[100005];
llint cnt[100005];

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	
	for(int i = 1; i <= n; i++) vec[x[i]].push_back(y[i]);
	for(int i = 1; i <= n; i++) vecx[y[i]].push_back(x[i]);
	
	for(int i = 1; i < 100005; i++){
		for(int j = 1; j < vec[i].size(); j++) uf.unite(vec[i][j-1], vec[i][j]);
	}
	for(int i = 1; i < 100005; i++){
		for(int j = 0; j < vec[i].size(); j++){
			S[uf.root(i)].insert(vecx[i][j]);
		}
		cnt[uf.root(i)]++;
	}
	
	llint ans = 0;
	for(int i = 1; i < 100005; i++){
		ans += S[i].size() * cnt[i];
	}
	ans -= n;
	cout << ans << endl;
	
	return 0;
}

Submission Info

Judge Result