B. Chemical table
One of the way to solve this problem is to interprete the cells in 2d matrix as an edge in the bipartite graph, that is a cell (i, j) is an edge between i of the left part and j of the right part.
将行号放一边,列号放一边构造一个二分图,如果表格中有一点(r,c)意味着二分图左端r向右端c连一条边。
Note, that each fusion operation (we have edges (r1, c1), (r1, c2), (r2, c1) and get edge (r2, c2)) doesn’t change the connected components of the graph.
题目中给的这个意思是不改变当前图的连通性。
然后需要求还需要最少的点数是的n+m个点联通(行n个点,列m个点)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template <class T=int> T rd()
{
T res=0;T fg=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}
while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
return res*fg;
}
const int N=400010;
int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int merge(int x,int y)
{
if(find(x)==find(y)) return 0;
fa[find(x)]=find(y);
return 1;
}
int n,m,q;
int main()
{
n=rd(),m=rd(),q=rd();
for(int i=1;i<=n+m;i++) fa[i]=i;
int ans=n+m-1;
while(q--)
{
int r=rd(),c=rd();
ans-=merge(r,c+n);
}
printf("%d\n",ans);
return 0;
}