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; }

總結

以上是生活随笔為你收集整理的codeforces1012 B. Chemical table（并查集+思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。