atcoder abc F - Must Be Rectangular!
程序员文章站
2022-03-15 22:41:18
...
题意:
有一个操作,对于一个矩阵的三个点,可以加上最后一个没有的点。
问对于已经有的点能够实现多少次这样的操作?
题解:
我们考虑图:
实际上一个可以操作的地方只要是连通的区域,就可以把这块区域的点填满。
蓝色为已有的点,红色是后来加上的点,可以通过一点点加进来。
只要在这个区域内的,线上的点都可以被填上。
求出每个块内,所有点在的横线和竖线个数,相乘就是所有点。
怎么求有多少个区域呢?我们可以利用并查集,把每个点的横坐标和纵坐标绑在一个集合里,这样以后出现相同竖线的和相同横线的都会被绑进来,形成一个大集合,但是单独计算的时候,只把竖线和横线单独计算。
最后减去已有的点即可。
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
const ULL base = 233;
const int N = 100005;
int n;
int f[201000];
ll val1[200100],val2[201000];
int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}
int main(){
cin>>n;
FOR(i,1,2*N)f[i]=i;
FOR(i,1,n){
int x,y;
scanf("%d%d",&x,&y);
f[find(x)]= find(y+N);
}
FOR(i,1,N)val1[find(i)]++;
FOR(i,N+1,2*N)val2[find(i)]++;
ll ans=0;
FOR(i,1,2*N){
ans+=val1[i]*val2[i];
//if(val1[i]*val2[i])cout<<ans<<" "<<i<<" "<<i-N<<endl;
}
printf("%lld\n",ans-n);
}