欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

atcoder abc F - Must Be Rectangular!

程序员文章站 2022-03-15 22:41:18
...

题意:
有一个操作,对于一个矩阵的三个点,可以加上最后一个没有的点。
问对于已经有的点能够实现多少次这样的操作?

题解:
我们考虑图:
实际上一个可以操作的地方只要是连通的区域,就可以把这块区域的点填满。
atcoder abc F - Must Be Rectangular!
蓝色为已有的点,红色是后来加上的点,可以通过一点点加进来。
只要在这个区域内的,线上的点都可以被填上。
求出每个块内,所有点在的横线和竖线个数,相乘就是所有点。

怎么求有多少个区域呢?我们可以利用并查集,把每个点的横坐标和纵坐标绑在一个集合里,这样以后出现相同竖线的和相同横线的都会被绑进来,形成一个大集合,但是单独计算的时候,只把竖线和横线单独计算。
最后减去已有的点即可。

#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);
}
相关标签: 并查集 思维