题目链接
思路：并查集裸题。并查集注意最后更新路径压缩。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6+10; int par[maxn],vis[maxn]; void init(int n) { for(int i=1;i<=n;i++) { par[i]=i; vis[i]=0; } } int fnd(int x) { if(par[x]==x) return x; return par[x]=fnd(par[x]); } bool same(int x,int y) { return fnd(x)==fnd(y); } void unite(int x,int y) { x=fnd(x); y=fnd(y); if(x!=y) par[x]=y; } int main() { int m,n,k,x,y; cin>>m>>n>>k; init(m*n); for(int i=0;i<k;i++) { cin>>x>>y; unite(x,y); } int ans=0; for(int i=1;i<=m*n;i++) fnd(i); for(int i=1;i<=m*n;i++) vis[par[i]]=1; for(int i=1;i<=m*n;i++) ans+=vis[i]; cout<<ans; return 0; }
