Codeforces 1012B Chemical table

题目链接http://codeforces.com/problemset/problem/1012/B

题意:给你n\times m的矩阵,刚开始有一些位置可以填满数,如果三个点在一个矩形的三个顶点上就可产生剩下的那个顶点,问最少加几个点使得最后的矩阵全部充满点。

思路:对于一个点(r,c),拆成行r和列c两个点,然后连边,可以发现三个点的时候三个点所在的行与列都已经互相可以两两到达即在一个即集合里,这时候剩下的点可以直接产生,所以只要最后行列都在一个集合里所有的点就都可以产生。我们对所有已存在的点行列连边,用并查集维护联通性,最后的答案就是联通块数量减一。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=200000+10;
int n,m,q,i,r,c,fa[N*2];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
int main(){
    read(n),read(m),read(q);
    for (i=1;i<=n+m;i++) fa[i]=i;
    int ans=n+m-1;
    for (;q--;){
        read(r),read(c);
        c+=n;
        r=Find(r),c=Find(c);
        if (r^c){
            fa[r]=c;
            ans--;
        }
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注